当前位置:网站首页>Contest3145 - the 37th game of 2021 freshman individual training match_ A: Prizes
Contest3145 - the 37th game of 2021 freshman individual training match_ A: Prizes
2022-07-06 15:10:00 【This question AC sleep again】
//
problem A: Prize
The time limit : 1.000 Sec Memory limit : 128 MB
Title Description
Na Zha, the Third Prince of King li of tota , High skill , He wants to catch up with the Olympic Games , Open a mind Olympic Games , The prize of the winner is refined “ helium -3” Crystal structure ;
This substance is abundant on the moon There is , It is colorless 、 Tasteless helium isotopes , It plays an important role in nuclear fusion research .
helium -3 Or a kind of Absolutely clean energy , Because it doesn't have the nature of releasing itself , Therefore, no radioactive waste will be produced . But if from The crystal will be transported back to earth on the moon ? Na Zha said : Use my belly pocket !
Of course, his belly pocket is vulnerable to solar wind and other factors Influence , The carrying capacity cannot exceed k(1<=k<=100000), Beyond that , The belly pocket won't fly ;
This k value Na Zha will tell you , It will also tell you the weight of each crystal . Your task is to make this belly bag transport more crystals at a time .
Input
There are two lines The first line has two positive integers n and k, Separated by a space . Express n Crystal , The maximum carrying capacity of the belly pocket is k. The second line has n No more than one. 10000 The positive integer , respectively n Weight of crystals , Use a space between numbers Grid separation .
Output
There is only one line , This line has only one positive integer , It means that nazha's belly pocket can be transported back at one time The maximum crystal weight of .
The sample input Copy
5 15
2 4 4 8 10
Sample output Copy
14
Tips
[ Data restrictions ]
40% The data of : 1<=n<=20
100% The data of : 1<=n<=100
//
// dp
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+6;
int a[111],dp[111][MAXN];
int main()
{
int n,k,i,j;
while( ~scanf("%d%d",&n,&k) )
{
memset( a,0,sizeof( a ) );
memset( dp,0,sizeof( dp ) );
for( i=1;i<=n;i++ ) scanf("%d",&a[i]);
for( i=1;i<=n;i++ )
{
for( j=1;j<=k;j++ )
{
if( j<a[i] ) dp[i][j]=dp[i-1][j];
else dp[i][j]=max( dp[i-1][j],dp[i-1][j-a[i]]+a[i] );
}
}
printf("%d\n",dp[n][k]);
}
return 0;
}
//
find:
01 How to solve it with one-dimensional array
边栏推荐
- Don't you even look at such a detailed and comprehensive written software test question?
- 软件测试工作太忙没时间学习怎么办?
- Description of Vos storage space, bandwidth occupation and PPS requirements
- Global and Chinese markets of Iam security services 2022-2028: Research Report on technology, participants, trends, market size and share
- Wang Shuang's detailed notes on assembly language learning I: basic knowledge
- What are the business processes and differences of the three basic business modes of Vos: direct dial, callback and semi direct dial?
- 软件测试面试要问的性能测试术语你知道吗?
- HackTheBox-Emdee five for life
- Collection集合与Map集合
- The four connection methods of JDBC are directly coded
猜你喜欢
CSAPP家庭作业答案7 8 9章
Wang Shuang's detailed learning notes of assembly language II: registers
MySQL数据库(四)事务和函数
几款开源自动化测试框架优缺点对比你知道吗?
The number of reversing twice in leetcode simple question
What level do 18K test engineers want? Take a look at the interview experience of a 26 year old test engineer
Install and run tensorflow object detection API video object recognition system of Google open source
Logstack introduction and deployment -- elasticstack (elk) work notes 019
Software testing interview summary - common interview questions
“Hello IC World”
随机推荐
CSAPP homework answers chapter 789
自动化测试中敏捷测试怎么做?
Zhejiang University Edition "C language programming experiment and exercise guide (3rd Edition)" topic set
Build your own application based on Google's open source tensorflow object detection API video object recognition system (II)
Leetcode simple question: check whether two strings are almost equal
Global and Chinese market of maleic acid modified rosin esters 2022-2028: Research Report on technology, participants, trends, market size and share
Statistics 8th Edition Jia Junping Chapter 2 after class exercises and answer summary
Sleep quality today 81 points
About the garbled code problem of superstar script
Cc36 different subsequences
Global and Chinese market of goat milk powder 2022-2028: Research Report on technology, participants, trends, market size and share
MySQL数据库(一)
Practical cases, hand-in-hand teaching you to build e-commerce user portraits | with code
Collection集合与Map集合
How to solve the poor sound quality of Vos?
自动化测试你必须要弄懂的问题,精品总结
Global and Chinese market for antiviral coatings 2022-2028: Research Report on technology, participants, trends, market size and share
Sorting odd and even subscripts respectively for leetcode simple problem
With 27K successful entry ByteDance, this "software testing interview notes" has benefited me for life
[pointer] octal to decimal