NC15880. Beautiful Land
描述
输入描述
There are multiple cases.
The first line is an integer T(T≤10), which is the number of test cases.
For each test case, the first line is two number n(1≤n≤100) and C(1≤C≤108), the number of seeds and the capacity of the land.
Then next n lines, each line contains two integer ci(1≤ci≤106) and vi(1≤vi≤100), the space cost and the value of the i-th tree.
输出描述
For each case, output one integer which means the max value of the trees that can be plant in the land.
示例1
输入:
1 3 10 5 10 5 10 4 12
输出:
22
Python3(3.5.2) 解法, 执行用时: 1940ms, 内存消耗: 3908K, 提交时间: 2018-05-11 00:19:16
from sys import stdin
rl = lambda l: tuple(map(int, l.split()))
rd = lambda: rl(input())
t = int(input())
inp = map(rl, stdin.readlines())
for _ in range(t):
n, C = next(inp)
dp = [0] + [0x3f3f3f3f] * (n * 100)
a = [next(inp) for i in range(n)]
c, v = zip(*a)
s = sum(v)
for i in range(n):
for j in range(s, -1, -1):
if j >= v[i]:
dp[j] = min(dp[j - v[i]] + c[i], dp[j])
for i in range(s, -1, -1):
if dp[i] <= C:
break
print(i)
C++14(g++5.4) 解法, 执行用时: 6ms, 内存消耗: 876K, 提交时间: 2020-04-26 17:18:40
#include<bits/stdc++.h>
using namespace std;
int t;
const int N=1e5+1000;
int w[N],v[N],n,m;
int f[N];
int main()
{
cin>>t;
while(t--)
{
scanf("%d %d",&n,&m);
memset(f,0x3f,sizeof f);
int sum=0;
for(int i=1;i<=n;i++)
{
scanf("%d %d",&w[i],&v[i]);
sum+=v[i];
}
f[0]=0;
for(int i=1;i<=n;i++)
{
for(int j=sum;j>=v[i];j--)
{
f[j]=min(f[j],f[j-v[i]]+w[i]);
}
}
for(int i=sum;i>=0;i--)
{
if(f[i]<=m)
{
cout<<i<<endl;
break;
}
}
}
}
C++11(clang++ 3.9) 解法, 执行用时: 17ms, 内存消耗: 4492K, 提交时间: 2020-02-28 22:48:19
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
int p[105],v[1005];
int main()
{
int n,s,t;
cin>>t;
while(t--)
{
int sum=0,ans=0;
cin>>n>>s;
vector<int >dp(1e6+5,inf);
for(int i=0;i<n;i++)
{
cin>>p[i]>>v[i];
sum+=v[i];
}
dp[0]=0;
for(int i=0;i<n;i++)
for(int j=sum;j>=v[i];j--)
{
dp[j]=min(dp[j],dp[j-v[i]]+p[i]);
if(dp[j]<=s&&ans<j) ans=j;
}
cout<<ans<<endl;
}
}