上次NOIP过后就没怎么写过代码了,算下来已经有一年多的时间了……

为了ACM,现在开始进行“康复训练”吧!

01背包 稍加魔改的问题

我发现WP居然不能上代码块,改天研究一下!!

Samples
Input Output
1
50
5
10
1 2 3 2 1 1 2 3 2 1
50
0
-45
32

 

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
template<class _T>inline void read(_T &_a)
{
bool f=0; char _c=getchar(); _a=0;
while(_c<'0'||_c>'9'){ if(_c=='-') f=1; _c=getchar(); }
while(_c>='0'&&_c<='9'){ _a=(_a<<3)+(_a<<1)-'0'+_c; _c=getchar(); }
if(f) _a=-_a;
}

int n,p[1001],m,M,lin;
bool dp[1046];

int main()
{
read(n);
while(n)
{
memset(dp,0,sizeof dp); dp[0]=true;
for (register int i=1;i<=n;++i) read(p[i]);
sort(p+1,p+n+1);
read(m);
M=m+p[n]-5; lin=m-5;
for (register int i=1;i<=n;++i)
for (register int j=m-5+p[i];j>=p[i];--j)
dp[j]|=dp[j-p[i]];
for (register int i=M;i>=0;--i)
if(dp[i]) { printf("%d\n",m-i); break; }
read(n);
}
return 0;
}

分类: 未分类