你不是A了吗
by lovely_fcukh @ 2023-07-16 21:06:03
@[lovely_fcukh](/user/335786) 这个是抄了题解的，然后因为我觉得我加了那两行continue的判断好像更稳妥，结果不知道为什么就WA了
by DaShabby @ 2023-07-16 21:14:06
。。。你这代码似乎是A了的那你份
by lovely_fcukh @ 2023-07-16 21:17:02
我是这样想的，如果前一行的
```
dp[(i+1)%2][j-IQ[i]]
```
结果为-inf，那么应该就说明前i-1个牛中没有组合能组合成
```
j-IQ[i]
```
的智商和的，所以可以pass。
但我就是不知道为什么这个反而还WA了
by DaShabby @ 2023-07-16 21:18:48
这个就是WA的
```
#include<bits/stdc++.h>
#define x first
#define y second
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int maxn=5e5+23;
int dp[2][maxn*2];
//dp[i][j]表示选第i头牛之后IQ为j时,EQ最高为多少
int IQ[maxn],EQ[maxn];
int zero=4e5;
void work(){
int n,m,k,u,v,w;
scanf("%d",&n);
for(int j=0;j<=8e5;j++)dp[0][j]=dp[1][j]=-inf;
dp[0][zero]=dp[1][0]=0;
for(int i=1;i<=n;i++)scanf("%d%d",&IQ[i],&EQ[i]);
for(int i=1;i<=n;i++){
if(IQ[i]>=0){
for(int j=IQ[i];j<=8e5;j++){
if(dp[(i+1)%2][j-IQ[i]]==-inf)continue; //该行被注释就过了
dp[i%2][j]=max(dp[(i+1)%2][j],dp[(i+1)%2][j-IQ[i]]+EQ[i]);
}
}
else{
for(int j=0;j<=8e5+IQ[i];j++){
if(dp[(i+1)%2][j-IQ[i]]==-inf)continue; //该行被注释就过了
dp[i%2][j]=max(dp[(i+1)%2][j],dp[(i+1)%2][j-IQ[i]]+EQ[i]);
}
}
}
int MAX=0;
for(int i=4e5;i<=8e5;i++){
if(dp[n%2][i]>=0)MAX=max(MAX,i-zero+dp[n%2][i]);
}
printf("%d\n",MAX);
}
int main()
{
int t=1;
// scanf("%d",&t);
while(t--)
work();
return 0;
}
by DaShabby @ 2023-07-16 21:20:07
对不起，你的回复没提示，还有我刚刚去给别人看代码了所以晚了点QAQ
by lovely_fcukh @ 2023-07-16 22:01:31
可以发现转移方程中有两种量，一个为 dp[(i+1)%2][j] 另一个为 dp[(i+1)%2][j-IQ[i]]+EQ[i]（注：接受值得数为 dp[i%2][j]），所以你还得加个特判，不然就少了 dp[(i+1)%2][j] 有非 -inf 值的情况。我帮你改了一下A了：
```
#include<bits/stdc++.h>
#define x first
#define y second
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int maxn=5e5+23;
int dp[2][maxn*2];
//dp[i][j]表示选第i头牛之后IQ为j时,EQ最高为多少
int IQ[maxn],EQ[maxn];
int zero=4e5;
void work(){
int n,m,k,u,v,w;
scanf("%d",&n);
for(int j=0;j<=8e5;j++)dp[0][j]=dp[1][j]=-inf;
dp[0][zero]=dp[1][0]=0;
for(int i=1;i<=n;i++)scanf("%d%d",&IQ[i],&EQ[i]);
for(int i=1;i<=n;i++){
if(IQ[i]>=0){
for(int j=IQ[i];j<=8e5;j++){
if(dp[(i+1)%2][j-IQ[i]]+EQ[i]==-inf&&dp[(i+1)%2][j]==-inf)continue; //该行被注释就过了
dp[i%2][j]=max(dp[(i+1)%2][j],dp[(i+1)%2][j-IQ[i]]+EQ[i]);
}
}
else{
for(int j=0;j<=8e5+IQ[i];j++){
if(dp[(i+1)%2][j-IQ[i]]+EQ[i]==-inf&&dp[(i+1)%2][j]==-inf)continue; //该行被注释就过了
dp[i%2][j]=max(dp[(i+1)%2][j],dp[(i+1)%2][j-IQ[i]]+EQ[i]);
}
}
}
int MAX=0;
for(int i=4e5;i<=8e5;i++){
if(dp[n%2][i]>=0)MAX=max(MAX,i-zero+dp[n%2][i]);
}
printf("%d\n",MAX);
}
int main()
{
int t=1;
// scanf("%d",&t);
while(t--)
work();
return 0;
}
```
by lovely_fcukh @ 2023-07-16 22:04:20
@[DaShabby](/user/672837)
by lovely_fcukh @ 2023-07-16 22:04:50
@[lovely_fcukh](/user/335786) 谢谢大佬，我明白了orz
by DaShabby @ 2023-07-18 20:34:52