codeforces #319 B - Modulo Sum (抽屉原理，dp)
背包还是理解的不够透彻．．
因为每次都是用那个一维形式的．
这道题的做法类似01背包.
此外还可以有一个优化…
当n>m的时候．．．根绝抽屉原理．．一定为yes..
复杂度可以从o(nm)优到 o(m^2)
1/*************************************************************************
2 > File Name: code/cf/#319/B.cpp
3 > Author: 111qqz
4 > Email: rkz2013@126.com
5 > Created Time: 2015年09月15日 星期二 19时54分44秒
6 ************************************************************************/
7
8#include<iostream>
9#include<iomanip>
10#include<cstdio>
11#include<algorithm>
12#include<cmath>
13#include<cstring>
14#include<string>
15#include<map>
16#include<set>
17#include<queue>
18#include<vector>
19#include<stack>
20#include<cctype>
21#define y1 hust111qqz
22#define yn hez111qqz
23#define j1 cute111qqz
24#define ms(a,x) memset(a,x,sizeof(a))
25#define lr dying111qqz
26using namespace std;
27#define For(i, n) for (int i=0;i<int(n);++i)
28typedef long long LL;
29typedef double DB;
30const int inf = 0x3f3f3f3f;
31const int N=1E3+7;
32int n,m;
33int a[N];
34int dp[N];
35void OneZeroPack(int cost,int value)
36{
37 for ( int v = m ; v--; v >=cost)
38 {
39 dp[v] = max(dp[v],dp[v-cost]+value);
40 }
41}
42int main()
43{
44 #ifndef ONLINE_JUDGE
45
46 #endif
47 cin>>n>>m;
48 if (n>=m)
49 {
50 puts("YES");
51 return 0;
52 }
53 int k = 0;
54 for ( int i = 0 ; i < n ; i++)
55 {
56 int x;
57 scanf("%d",&x);
58 if (x>m) continue; //大于背包容量的肯定直接舍去
59 k++;
60 a[k] = x;
61 }
62 // for ( int i = 1 ; i <= k ; i++) cout<<"a[i]:"<<a[i]<<endl;
63 for ( int i = 0 ; i <= m ; i++)
64 dp[i] = -inf;
65 dp[0] = 0 ;
66 for ( int i = 1 ; i <= k ; i++)
67 {
68 OneZeroPack(a[i],a[i]);
69 }
70 for ( int i = 0 ; i <= m ; i++) cout<<i<<" "<<dp[i]<<endl;
71 if (dp[m]==-inf)
72 {
73 puts("NO");
74 }
75 else
76 {
77 puts("YES");
78 }
79
80
81 #ifndef ONLINE_JUDGE
82 fclose(stdin);
83 #endif
84 return 0;
85}