using namespace std;
int n,m,i,j;
int a[5001],b[5001][3];
int f[5001][2];
bool q[5001][2][5001];
void ff(int x,int y){
for(j=1;j<=n;j++){q[i][x][j]=q[i-1][y][j];}
}
int main(){
cin>>n>>m;
memset(f,0,sizeof(f));
memset(q,0,sizeof(q));
for(i=1;i<=n;i++)cin>>a[i];
for(i=1;i<=m;i++){cin>>b[i][0]>>b[i][1]>>b[i][2];}
for(i=1;i<=m;i++){
if(f[i-1][0]<f[i-1][1])
{f[i][0]=f[i-1][1];ff(0,1);}
else
{f[i][0]=f[i-1][0];ff(0,0);}
if((f[i-1][0]+b[i][2]-a[b[i][0]]*(1-q[i-1][0][b[i][0]])-a[b[i][1]]*(1-q[i-1][0][b[i][1]]))<(f[i-1][1]+b[i][2]-a[b[i][0]]*(1-q[i-1][1][b[i][0]])-a[b[i][1]]*(1-q[i-1][1][b[i][1]])))
{f[i][1]=(f[i-1][1]+b[i][2]-a[b[i][0]]*(1-q[i-1][1][b[i][0]])-a[b[i][1]]*(1-q[i-1][1][b[i][1]]));ff(1,1);}
else
{f[i][1]=(f[i-1][0]+b[i][2]-a[b[i][0]]*(1-q[i-1][0][b[i][0]])-a[b[i][1]]*(1-q[i-1][0][b[i][1]]));ff(1,0);}
q[i][1][b[i][0]]=1;q[i][1][b[i][1]]=1;
cout<<f[i][0]<<f[i][1]<<endl;
}
cout<<max(f[m][0],f[m][1]);
system("pause");
return 0;
}
本题我用了01背包的思想，用数组q记录每次动规后的中转站建成情况（0代表没建，1代表建了）
样例过了
然而
。。。。。。。。。
测试结果1: 测试结果错误.错误结果为:0
正确结果应为:68
测试结果2: 测试结果错误.错误结果为:26
正确结果应为:157
测试结果3: 测试结果错误.错误结果为:6
正确结果应为:890
测试结果4: 测试结果错误.错误结果为:20
正确结果应为:787
测试结果5: 测试结果错误.错误结果为:170
正确结果应为:1623
测试结果6: 测试结果错误.错误结果为:113
正确结果应为:688
测试结果7: 测试结果错误.错误结果为:86
正确结果应为:1312
测试结果8: 测试结果错误.错误结果为:25
正确结果应为:271
测试结果9: 测试结果错误.错误结果为:25
正确结果应为:32646
测试结果10: 测试结果错误.错误结果为:25
正确结果应为:29752