cf-366C-Dima and Salad - html/css语言栏目：html.css - 自学

把问题重新定义为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;  
}