$01$ 背包变形
题目传送门
虽然我也不知道为什么被卡了反正就是听取WA声一片
扫描第$i$件物品能够得到$t_i+1$件物品，则将题目转化为：
一共有$n$件物品，第$i$件物品的体积为$t_i+1$，价值为$c_i$。
$AC\ Code$：
查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int M=2005,N=4005;
int n,t[M],v;
ll c[M],dp[N],ans=2e12;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%lld",&t[i],&c[i]);
t[i]++;
v=max(v,t[i]);
}
v+=n;
memset(dp,0x7f,sizeof(dp));dp[0]=0;
for(int i=1;i<=n;i++)
for(int j=v;j>=t[i];j--)
dp[j]=min(dp[j],dp[j-t[i]]+c[i]);
for(int i=n;i<=v;i++)
ans=min(ans,dp[i]);
printf("%lld",ans);
return 0;
}
|