游客 注册 | 登录
中文 | En

2583 - 奖品

  

<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

提示

 



<b><span style="font-family:宋体;">【数据限制】</span></b><b><span style="font-family:Verdana;"></span></b>







<span style="font-family:Verdana;">40%</span><span style="font-family:宋体;">的数据：</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;">20</span><span style="font-family:宋体;">。</span><span style="font-family:Verdana;"></span>







<span style="font-family:Verdana;">100%</span><span style="font-family:宋体;">的数据：</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;">100</span><span style="font-family:宋体;">。</span><span style="font-family:Verdana;"></span>

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;
}

提示

  

<b><span style="font-family:宋体;">【数据限制】</span></b><b><span style="font-family:Verdana;"></span></b>


<span style="font-family:Verdana;">40%</span><span style="font-family:宋体;">的数据：</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;">20</span><span style="font-family:宋体;">。</span><span style="font-family:Verdana;"></span>


<span style="font-family:Verdana;">100%</span><span style="font-family:宋体;">的数据：</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;">100</span><span style="font-family:宋体;">。</span><span style="font-family:Verdana;"></span>

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题