poj 2392 (Space Elevator) 1276 (Cash Machine)變形背包

poj 2392 (Space Elevator) 1276 (Cash Machine)變形背包

這道題跟coins很像，看來樓教主的男人八題果然不簡單。

進行coins式的背包處理就好了。

2392

#include
#include
#include
#include
#include
#define max(a,b) ((a)>(b)?(a):(b))
typedef long long ll;
using namespace std;
const int maxn=41000;
struct P
{
    int a,b,c;
}p[maxn];
bool cmp( const struct P &a,const struct P&b)
{
    return a.bdp[j]  )
                {
                    use[j]=use[j-p[i].a]+1;
                    dp[j]=dp[j-p[i].a]+p[i].a;
                    maxh=max(maxh,dp[j]);
                }
            }
        }
        cout<

1276
#include
#include
#include
#include
#include
#define max(a,b) ((a)>(b)?(a):(b))
typedef long long ll;
using namespace std;
const int maxn=10+1000;
struct P
{
    int a,c;
}p[maxn];

int dp[maxn*1000],use[maxn*1000];
int n,m,T;
int K;
int main()
{
    while(~scanf("%d",&K))
    {
        int maxh=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
                scanf("%d%d",&p[i].c,&p[i].a);

        memset(dp,-1,sizeof(dp));
        dp[0]=0;
        for(int i=1;i<=n;i++)
        {
            memset(use,0,sizeof(use));
            for(int j=p[i].a;j<=K;j++)
            {
                if( dp[j-p[i].a]!=-1 && use[j-p[i].a]dp[j]  )
                {
                    use[j]=use[j-p[i].a]+1;
                    dp[j]=dp[j-p[i].a]+p[i].a;
                    maxh=max(maxh,dp[j]);
                }
            }
        }
        cout<