HDU 5074 Hatsune Miku（dp）(二)
s 1e-8 using namespace std; #define N 105 int b[N][N],a[N]; int n,m; int dp[N][N]; void solve() { int i,j,k; memset(dp,0,sizeof(dp)); for(i=2;i<=n;i++) if(a[i]<0) //bug就在这里，没有对a[i-1]分类，就是a[i-1]为定值，虽然dp[i-1][x]为0，但是b[x][j]//很大,所以需要严格的分类 { for(j=1;j<=m;j++) for(k=1;k<=m;k++) dp[i][j]=max(dp[i][j],dp[i-1][k]+b[k][j]); } else { if(a[i-1]>0) { dp[i][a[i]]=dp[i-1][a[i-1]]+b[a[i-1]][a[i]]; } else { for(k=1;k<=m;k++) dp[i][a[i]]=max(dp[i][a[i]],dp[i-1][k]+b[k][a[i]]); } } } int main() { int i,j,t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); memset(b,0,sizeof(b)); for(i=1;i<=m;i++) for(j=1;j<=m;j++) scanf("%d",&b[i][j]); for(i=1;i<=n;i++) scanf("%d",&a[i]); solve(); int ans=0; for(i=1;i<=m;i++) ans=max(ans,dp[n][i]); printf("%d\n",ans); } return 0; }