首页 > 代码库 > NOIP2017模拟赛 senior 6.29 T3 Gift（gift）
NOIP2017模拟赛 senior 6.29 T3 Gift（gift）
NOIP2017模拟赛 senior 6.29 T3 Gift（gift）
Description
Input
Output
这道题的难度相对来说并没有第二题恼火，但还是很难搞的。
那么这道题读完题目还是比较好看出这是一道背包的变形题。
因为每一份礼物都是取或者不取两个状态，所以，01背包好理解吧。
然后题目中说选到不能选为止，所以我们先将读入的礼物的价值排个序，然后从大到小我们去选取礼物，如果当前礼物价值大于剩余财富，那么我们就不能选了对吧。
于是就这样一层层的向下进行动归。
每一次我们处理当前层的DP数组，将答案加上上一层DP数组的值。这样我们就合理的处理完了整个DP数组。
所以说，这道题目的主要思想还是01背包，但是其中还加上了我们根据题意所得的排序预处理。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #define INT_MAX_ 0x7fffffff 7 #define LONG_MAX_ 0x7fffffffffffffffll 8 #define pi acos(-1) 9 #define N 101010 #define mod 1000000711 using namespace std;12 13 inline int read()14 {15 int data=http://www.mamicode.com/0,w=1;16 char ch=0;17 while(ch!=‘-‘ && (ch<‘0‘ || ch>‘9‘)) ch=getchar();18 if(ch==‘-‘) w=-1,ch=getchar();19 while(ch>=‘0‘ && ch<=‘9‘) data=http://www.mamicode.com/data*10+ch-‘0‘,ch=getchar();20 return data*w;21 }22 23 inline void write(int x)24 {25 if(x<0) putchar(‘-‘),x=-x;26 if(x>9) write(x/10);27 putchar(x%10+‘0‘);28 }29 30 int n,m;31 int Val[N],Sum[N],dp[N][N],ans;32 33 int main()34 {35 freopen("gift.in","r",stdin);36 freopen("gift.out","w",stdout);37 38 n = read();39 m = read();40 for(int i = 1; i <= n; i++)41 {42 Val[i] = read();43 }44 sort(Val+1,Val+1+n);45 for(int i = 1; i <= n; i++)46 {47 Sum[i] = Sum[i-1] + Val[i];48 }49 dp[n+1][m] = 1;50 for(int i = n; i >= 1; i--)51 {52 for(int j = Sum[i-1]; j < min(m + 1, Val[i] + Sum[i-1]); j++)53 {54 ans = (ans + dp[i+1][j]) % mod;55 }56 for(int j = m; j >= 0; j--)57 {58 if(j + Val[i] <= m) dp[i][j] = dp[i+1][j+Val[i]];59 dp[i][j] = (dp[i][j] + dp[i+1][j]) % mod;60 }61 }62 if(ans == 0) ans = 1;63 write(ans);64 65 return 0;66 }
NOIP2017模拟赛 senior 6.29 T3 Gift（gift）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。