第一种:
题目大意是给你m个note,n个数,得分是v[a[i]][a[i+1]]的总和,如果说a[i]是-1的话代表可以放入1~m中任一个note,否则必须放他给的note号。
问:最大的得分是多少?
设dp(i,j)代表到第i个位置,放标号为j的note
那么
如果说a[i+1]<0,那么dp(i,j) = max( dp(i,j) , dp(i+1,k)+a[j][k] );
否则dp(i,j) = dp(i+1,b[i+1]) + v[j][b[i+1]];
/*
在第i个位置,用第j个note
b[i+1] < 0 dp(i,j) = max(d(i,j), d(i+1, k) + a[j][k]);
else dp(i,j) = d(i+1, b[j+1]) + a[j][b[i+1]]);
*/
#include<iostr......
阅读全文