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