NC14370. 入学考试
描述
输入描述
第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
输出描述
包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
示例1
输入:
70 3 71 100 69 1 1 2
输出:
3
说明:
对于30%的数据，M <= 10；Python3 解法, 执行用时: 174ms, 内存消耗: 9224K, 提交时间: 2022-10-31 10:37:19
t,n=map(int,input().split())
ls=[[0,0]]
for i in range(n):
time,value=map(int,input().split())
ls.append([time,value])
dp=[[0 for i in range(t+1)] for j in range(n+1)]
for i in range(1,n+1):
for j in range(1,t+1):
if j < ls[i][0]:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j],ls[i][1]+dp[i-1][j-ls[i][0]])
print(dp[-1][-1])
C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 592K, 提交时间: 2020-04-17 22:49:41
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
int n, v;
cin>>v>>n;
int dp[v+1];
memset(dp,0,sizeof(dp));
for (int i=0;i<n;i++)
{
int ci,value;
cin>>ci>>value;
for (int j=v;j>=ci;j--)
{
dp[j]=max(dp[j],dp[j-ci]+value);
}
}
cout<<dp[v];
return 0;
}
C++(clang++11) 解法, 执行用时: 3ms, 内存消耗: 388K, 提交时间: 2021-03-17 15:39:16
#include <iostream>
using namespace std;
int f[1001];
int main()
{
int t,n,j,i,x,y;
cin>>t>>n;
for (i=1;i<=n;i++)
{
cin>>x>>y;
for (j=t;j>=x;j--)
f[j]=max(f[j],f[j-x]+y);
}
cout<<f[t];
return 0;
}