题解 P1910 【L国的战斗之间谍】
本题背包
我在刷水题时，先刷了一个一维背包
P2722 总分 Score Inflation\
自我感觉良好 （看了题解）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#define ll long long
using namespace std;
ll c[110000],w[110000];
ll n,m,i,j,sum,dp[11000];
int main()
{
scanf("%lld%lld",&m,&n);
for(i=1;i<=n;i++)
scanf("%lld%lld",&w[i],&c[i]);
for(i=1;i<=n;i++)
{
for(j=c[i];j<=m;j++)
{
dp[j]=max(dp[j],dp[j-c[i]]+w[i]);
}
}
printf("%lld\n",dp[m]);
//printf("%d\n",clock());
return 0;
}
so easy
Than......
这道题我改了改
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#define ll long long
using namespace std;
ll n,m,x,w[1100],b[1100],c[1100],dp[1100][1100],i,j,k;
int main()
{
scanf("%lld%lld%lld",&n,&m,&x);
for(i=1;i<=n;i++)scanf("%lld%lld%lld",&w[i],&b[i],&c[i]);
for(i=1;i<=n;i++)
{
for(j=b[i];j<=m;j++)
{
for(k=c[i];k<=x;k++)
{
dp[j][k]=max(dp[j][k],dp[j-b[i]][k-c[i]]+w[i]);
}
}
}
printf("%lld\n",dp[m][x]);
//printf("%d\n",clock());
return 0;
}
？？？？？？？？？？？？
卧槽卧槽卧槽卧槽卧槽卧槽卧槽卧槽
只能看题解了
手打的正解：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#define ll long long
using namespace std;
ll n,m,x,w[1100],b[1100],c[1100],dp[1100][1100],i,j,k;
int main()
{
scanf("%lld%lld%lld",&n,&m,&x);
for(i=1;i<=n;i++)scanf("%lld%lld%lld",&w[i],&b[i],&c[i]);
for(i=1;i<=n;i++)
{
for(j=m;j>=b[i];j--)
{
for(k=x;k>=c[i];k--z)
{
dp[j][k]=max(dp[j][k],dp[j-b[i]][k-c[i]]+w[i]);
}
}
}
printf("%lld\n",dp[m][x]);
//printf("%d\n",clock());
return 0;
}