NYOJ 325 zb的生日 【dp问题】
发布时间：2020-12-16 22:37:26 所属栏目：大数据 来源：网络整理
导读：原文链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=325 这是一个可以用动态规划解决的题，可以看成是01背包的变形吧。。尽管出题人原意可能是让我们用搜索做的，但由于时间卡的不紧，于是我们可以水过。。。。本人用dp以2996ms水过（题目时间限制
原文链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=325这是一个可以用动态规划解决的题，可以看成是01背包的变形吧。。尽管出题人原意可能是让我们用搜索做的，但由于时间卡的不紧，于是我们可以水过。。。。本人用dp以2996ms水过（题目时间限制是3000ms）。。ac后看看本题排名就悲剧了，倒数第一。。⊙﹏⊙。。不扯废话了，看代码吧。。#include<stdio.h>
#include<algorithm>
int main()
{
int a,b,n,m,v;
while(scanf("%d",&v)!=EOF)
{
int yi[100001]={0};
int ok[10000];
int sum=0,sum1;
for(a=1;a<=v;a++)
{
scanf("%d",&ok[a]);
sum+=ok[a];
}
sum1=sum/2;
for(b=1;b<=v;b++)
{
for(m=sum1;m>=ok[b];m--)
{
if(yi[m]<(yi[m-ok[b]]+ok[b]))
yi[m]=yi[m-ok[b]]+ok[b];
}
}
printf("%dn",sum-2*yi[sum1]);
}
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |