2583 - 奖品
时间限制 : 1 秒
内存限制 : 128 MB
<span style="font-family:宋体;">托塔李天王的三太子那吒，本领高强，他要赶在奥林匹克运动会之际，开一个头脑奥林匹克比赛，获胜者的奖品就是经过提练后的“氦</span><span style="font-family:Verdana;">-3</span><span style="font-family:宋体;">”晶结体；该物质在月球上大量存在，是一种无色、无味的氦气同位素，它在核聚变研究中有重要作用。氦</span><span style="font-family:Verdana;">-3</span><span style="font-family:宋体;">还是一种绝对清洁的能源，因为它本身不带放射性，因此不会产生任何放射性废料。可是如何从月球上将该晶体运回地球呢？那吒说：用我的</span><span style="font-family:宋体;">肚兜吧！当然他的肚兜易受太阳风等因素的影响，载重量不能超过</span><span style="font-family:Verdana;">K(</span><span style="font-family:Verdana;">1</span><span style="font-family:宋体;">≤</span><span style="font-family:Verdana;">n</span><span style="font-family:宋体;">≤</span><span style="font-family:Verdana;">100000)</span><span style="font-family:宋体;">，超过这个值，肚兜就不会飞了；这个</span><span style="font-family:Verdana;">K</span><span style="font-family:宋体;">值那吒会告诉你的，同时还会告诉你每一个晶体的重量。</span><span style="font-family:Verdana;"></span>
<span style="font-family:宋体;">你的任务是使这个肚兜一次能运回更多的晶体。</span><span style="font-family:Verdana;"></span>
题目输入
<span style="font-family:宋体;">有两行：</span><span style="font-family:Verdana;"></span>
<span style="font-family:宋体;">第一行有</span><span style="font-family:宋体;">两个正整数</span><span style="font-family:Verdana;">n</span><span style="font-family:宋体;">和</span><span style="font-family:Verdana;">k</span><span style="font-family:宋体;">，用一个空格隔开。表示有</span><span style="font-family:Verdana;">n</span><span style="font-family:宋体;">个晶体，肚兜最大载重量为</span><span style="font-family:Verdana;">k</span><span style="font-family:宋体;">。</span><span style="font-family:Verdana;"></span>
<span style="font-family:宋体;">第二行有</span><span style="font-family:Verdana;">n</span><span style="font-family:宋体;">个不超过</span><span style="font-family:Verdana;">10000</span><span style="font-family:宋体;">的正整数，分别表示</span><span style="font-family:Verdana;">n</span><span style="font-family:宋体;">个晶体的重量，数与数之间用一个空格隔开。</span><span style="font-family:Verdana;"></span>
题目输出
<span style="font-family:宋体;">只有一行，</span><span style="font-family:宋体;">该行只有一个正整数，表示那吒的肚兜一次能运回的晶体重量的最大值。</span><span style="font-family:Verdana;"></span>
输入/输出样例
输入格式
5 15 2 4 4 8 10
输出格式
14
C++解答
#include<cstdio> #include<cstring> using namespace std; int t[110000]; int f[110000]; int mymax(int x,int y) { return x>y?x:y; } int main() { int n,T; while(scanf("%d%d",&n,&T)!=EOF) { for(int i=1;i<=n;i++) scanf("%d",&t[i]); memset(f,-1,sizeof(f)); f[0]=0; for(int i=1;i<=n;i++) { for(int j=T;j>=t[i];j--) { if(f[j-t[i]]!=-1) { f[j]=mymax(f[j],f[j-t[i]]+t[i]); } } } int ans=0; for(int i=1;i<=T;i++) ans=mymax(ans,f[i]); printf("%d\n",ans); } return 0; }