购买第i件物品可以获得t[i]+1件物品，转化为01背包问题
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define inf 1e18
#define inc 0xcfcfcfcf
#define N 4007
#define M 500007
#define mod 1000000007
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
using namespace std;
struct Node
{
int t,c;
}a[N];
int T=1,n,mxv;
int f[N];
bool Solve()
{
//freopen("test.in","r",stdin);
scanf("%lld",&n);
for(int i=1;i<=n;++i)
scanf("%lld%lld",&a[i].t,&a[i].c),mxv=max(mxv,a[i].t);
memset(f,0x3f,sizeof(f));
mxv+=n;
f[0]=0;
for(int i=1;i<=n;++i)
{
for(int j=mxv;j>=a[i].t+1;--j)
f[j]=min(f[j],f[j-a[i].t-1]+a[i].c);
}
int ans=inf;
for(int i=mxv;i>=n;--i)
ans=min(ans,f[i]);
printf("%lld\n",ans);
return true;
}
signed main()
{
//scanf("%lld",&T);
while(T--)
if(!Solve())
printf("-1\n");
return 0;
}
/*
-std=c++11
-std=c99
*/