网站地图    收藏   

主页 > 前端 > css教程 >

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

来源:自学PHP网    时间:2015-04-14 14:51 作者: 阅读:

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

 

 

自学PHP网专注网站建设学习,PHP程序学习,平面设计学习,以及操作系统学习

京ICP备14009008号-1@版权所有www.zixuephp.com

网站声明:本站所有视频,教程都由网友上传,站长收集和分享给大家学习使用,如由牵扯版权问题请联系站长邮箱904561283@qq.com

添加评论