HDU 5074 Hatsune Miku(简单二维dp)(二)
<= n; i++) for(int j = 1; j <= n; j++) scanf("%d",&mp[i][j]); for(int i = 1; i <= m; i++) scanf("%d",&num[i]); memset(dp, 0, sizeof(dp)); for(int i = 2; i <= m; i++) { if(num[i-1] == -1) { if(num[i] == -1) { for(int j = 1; j <= n; j++) for(int k = 1; k <= n; k++) dp[i][k] = max(dp[i-1][j]+mp[j][k], dp[i][k]); continue; } for(int j = 1; j <= n; j++) dp[i][num[i]] = max(dp[i][num[i]], dp[i-1][j]+mp[j][num[i]]); continue; } if(num[i] == -1) { for(int j = 1; j <= n; j++) dp[i][j] = max(dp[i][j], dp[i-1][num[i-1]]+mp[num[i-1]][j]); continue; } dp[i][num[i]] = dp[i-1][num[i-1]]+mp[num[i-1]][num[i]]; } int Max = 0; for(int i = 1; i <= n; i++) Max = max(Max, dp[m][i]); cout<