复杂度 nmk 空间复杂度nm
典型的二维背包问题
dp[i][j]表示用i个精灵球,消耗j点体力可以抓到的最多精灵
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int maxn=1010;
int dp[maxn][maxn],v[maxn],w[maxn];
int n,m,k;
int main()
{
scanf("%d%d%d",&n,&m,&k);m--;
for(int i=1;i<=k;i++)scanf("%d%d",&v[i],&w[i]);
for(int i=1;i<=k;i++)
for(int j=n;j;j--)
for(int l=m;l;l--)if(j>=v[i]&&l>=w[i])dp[j][l]=max(dp[j][l],dp[j-v[i]][l-w[i]]+1);
int ans1=0,ans2=0;for(int i=0;i<=m;i++)if(dp[n][i]>ans1)ans1=dp[n][i],ans2=i;
printf("%d %d\n",ans1,m-ans2+1);
return 0;
}
可以直接读入的时候操作,这样子时间空间复杂度都会降把。
这点不影响常数