#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,sum,x[105],y[105],z[105];
ll f[105][100005];
//f[i][j] 表示小信前 i 个选区获得 j 票，最少得有多少人从小友转向小信
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d%d",&x[i],&y[i],&z[i]);
memset(f,-0x3f,sizeof(f));
f[0][0]=0;
for(int i=1;i<=n;i++){
sum+=z[i];
for(int j=0;j<=sum;j++) f[i][j]=f[i-1][j];
if(x[i]>y[i]){
for(int j=z[i];j<=sum;j++) f[i][j]=f[i-1][j-z[i]];
}
else{
for(int j=z[i];j<=sum;j++){
f[i][j]=max(f[i-1][j],f[i-1][j-z[i]]+(y[i]-x[i]+1)/2);
}
}
}
for(int i=(sum+1)/2;i<=sum;i++){
if(f[n][i]!=f[0][1]){
printf("%lld",f[n][i]);
return 0;
}
}
return 0;
}
应该是这里
f[i][j]=max(f[i-1][j],f[i-1][j-z[i]]+(y[i]-x[i]+1)/2);
这里(y[i]-x[i]+1)/2可能会是负数，要与0取最大值（可能不对）
else 的时候说明 y_i>x_i 啊，你再看看
那里要取min吧
不对啊，小信最多可以获得1e9张票，会爆空间，dp需要重构
答案因该是(sum+1)/2~sum中的最小值，还有，dp转移公式需要取min
初始化写多少
0x3f
过了吗？
不是会超过1e9吗
0x3f吗？