cf-366C-Dima and Salad

当前位置 : 首页 > 网页制作 > CSS > cf-366C-Dima and Salad

cf-366C-Dima and Salad

来源: 作者: 时间:2016-01-28 09:27
把问题重新定义为c=a-b*k;寻找一系列c为0的时候a最大的值。因为c可正可负。所以把c正的01背包一次。把c负的01背包一次。当二者相等的时候,把a相加,取最大值。 includestdio h includestri
把问题重新定义为c=a-b*k;
寻找一系列c为0的时候a最大的值。
因为c可正可负。
所以把c正的01背包一次。
把c负的01背包一次。
当二者相等的时候,把a相加,取最大值。
 
#include<stdio.h>  
#include<string.h>  
#include<algorithm>  
#include<iostream>  
using namespace std;  
#define INF 99999999  
int n,k,i,j;  
int num[101];  
int dp1[100001];  
int dp2[100001];  
int as[1001];  
int bs[1001];  
int main()  
{  
    int a,b;  
    while(~scanf("%d%d",&n,&k))  
    {  
        for(i=0;i<=100000;i++)dp1[i]=dp2[i]=-INF;  
        dp1[0]=dp2[0]=0;  
        for(i=1;i<=n;i++)scanf("%d",&as[i]);  
        for(j=1;j<=n;j++)scanf("%d",&bs[j]);  
        for(i=1;i<=n;i++)  
        {  
            a=as[i];  
            b=bs[i];  
            num[i]=a-b*k;  
            if(num[i]<0)  
            {  
                num[i]=-num[i];  
                for(j=100000;j>=num[i];j--)  
                {  
                    dp2[j]=max(dp2[j],dp2[j-num[i]]+a);  
                }  
            }  
            else  
            {  
                for(j=100000;j>=num[i];j--)  
                {  
                    dp1[j]=max(dp1[j],dp1[j-num[i]]+a);  
                }  
            }  
        }  
        int maxn;  
        maxn=-1;  
        for(i=10000;i>=0;i--)  
        {  
            maxn=max(maxn,dp1[i]+dp2[i]);  
        }  
        if(maxn==0)maxn=-1;  
        cout<<maxn<<endl;  
    }  
    return 0;  
}  

 

 
Tag:
网友评论

<