hdu 1224

it2022-05-06  14

郁闷死啦,一道简单的DP,搞了好几个小时,结果输出错了,反序了,都怪测试例子是三个数,反序了也不知道呀,也怪自己……………………

#include<iostream> #include<string> using namespace std; int p[105],f[105],dp[105],ans[105]; bool map[105][105]; int main() { int a,b,n,m,cas,t=0; cin>>cas; while(cas--) { cin>>n; for(int i=1;i<=n;i++) cin>>p[i]; p[n+1]=0; memset(map,0,sizeof(map)); memset(dp,0,sizeof(dp)); cin>>m; for(int i=0;i<m;i++) { cin>>a>>b; map[a][b]=1; } f[1]=-1; for(int i=2;i<=n+1;i++) { for(int j=1;j<i;j++) if(map[j][i]&&p[i]+dp[j]>dp[i]) { dp[i]=p[i]+dp[j]; f[i]=j; } } int k=n+1,i=0; while(f[k]!=-1) { ans[i++]=f[k]; k=f[k]; } if(t++) cout<<endl; cout<<"CASE "<<t<<"#"<<endl<<"points : "<<dp[n+1]<<endl; cout<<"circuit : "; for(int j=i-1;j>=0;j--) cout<<ans[j]<<"->"; cout<<1<<endl; } return 0; }

转载于:https://www.cnblogs.com/nanke/archive/2011/08/10/2133139.html

相关资源:数据结构—成绩单生成器

最新回复(0)