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}

相关文章