纪中OJ算法模块动态规划专题练习第一部分

//挖地雷 #include<bits/stdc++.h> using namespace std; int main() { long f[201]={0},w[201],c[201]={0}; bool a[201][201]={0}; long i,j,n,x,y,l,k,maxx; memset(f,0,sizeof(f)); memset(c,0,sizeof(c)); memset(a,false,sizeof(a)); cin>>n; for (i=1;i<=n;i++) cin>>w[i]; do { cin>>x>>y; if ((x!=0)&&(y!=0)) a[x][y]=true; }while ((x!=0)||(y!=0)); f[n]=w[n]; for (i=n-1;i>=1;i--) { l=0;k=0; for (j=i+1;j<=n;j++) if ((a[i][j])&&(f[j]>l)) { l=f[j]; k=j; } f[i]=l+w[i]; c[i]=k; } k=1; for (j=2;j<=n;j++) if (f[j]>f[k]) k=j; maxx=f[k]; cout<<k; k=c[k]; while (k!=0) { cout<<"-"<<k; k=c[k]; } cout<<endl; cout<<maxx<<endl; }