Today you want to compose a song, which is just a sequence of notes. There are only m different notes provided in the package. And you want to make a song with n notes.
Also, you know that there is a system to eva luate the beautifulness of a song. FZ??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vciBlYWNoIHR3byBjb25zZWN1dGl2ZSBub3RlcyBhIGFuZCBiLCBpZiBiIGNvbWVzIGFmdGVyIGEsIHRoZW4gdGhlIGJlYXV0aWZ1bG5lc3MgZm9yIHRoZXNlIHR3byBub3RlcyBpcyBldmFsdWF0ZWQgYXMgc2NvcmUoYSwgYikuPGJyPgo8YnI+ClNvIHRoZSB0b3RhbCBiZWF1dGlmdWxuZXNzIGZvciBhIHNvbmcgY29uc2lzdGluZyBvZiBub3RlcyBhPHN1Yj4xPC9zdWI+LCBhPHN1Yj4yPC9zdWI+LCAuIC4gLiAsIGE8c3ViPm48L3N1Yj4sIGlzIHNpbXBseSB0aGUgc3VtIG9mIHNjb3JlKGE8c3ViPmk8L3N1Yj4sIGE8c3ViPmkmIzQzOzE8L3N1Yj4pIGZvciAxIKHcIGkgodwgbiAtIDEuPGJyPgo8YnI+Ck5vdywgeW91IGZpbmQgdGhhdCBhdCBzb21lIHBvc2l0aW9ucywgdGhlIG5vdGVzIGhhdmUgdG8gYmUgc29tZSBzcGVjaWZpYyBvbmVzLCBidXQgYXQgb3RoZXIgcG9zaXRpb25zIHlvdSBjYW4gZGVjaWRlIHdoYXQgbm90ZXMgdG8gdXNlLiBZb3Ugd2FudCB0byBtYXhpbWl6ZSB5b3VyIHNvbmehr3MgYmVhdXRpZnVsbmVzcy4gV2hhdCBpcyB0aGUgbWF4aW11bSBiZWF1dGlmdWxuZXNzIHlvdSBjYW4gYWNoaWV2ZT8KIAo8YnI+CklucHV0ClRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgVCAoVCCh3CAxMCksIGRlbm90aW5nIHRoZSBudW1iZXIgb2YgdGhlIHRlc3QgY2FzZXMuPGJyPgo8YnI+CkZvciBlYWNoIHRlc3QgY2FzZSwgdGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzIG4oMSCh3CBuIKHcIDEwMCkgYW5kIG0oMSCh3CBtIKHcIDUwKSBhcyBtZW50aW9uZWQgYWJvdmUuIFRoZW4gbSBsaW5lcyBmb2xsb3csIGVhY2ggb2YgdGhlbSBjb25zaXN0aW5nIG9mIG0gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzLCB0aGUgai10aCBpbnRlZ2VyIGluIHRoZSBpLXRoIGxpbmUgZm9yIHNjb3JlKGksIGopKCAwIKHcIHNjb3JlKGksIGopIKHcIDEwMCkuCiBUaGUgbmV4dCBsaW5lIGNvbnRhaW5zIG4gaW50ZWdlcnMsIGE8c3ViPjE8L3N1Yj4sIGE8c3ViPjI8L3N1Yj4sIC4gLiAuICwgYTxzdWI+bjwvc3ViPiAoLTEgodwgYTxzdWI+aTwvc3ViPiCh3CBtLCBhPHN1Yj5pPC9zdWI+IKHZIDApLCB3aGVyZSBwb3NpdGl2ZSBpbnRlZ2VycyBzdGFuZCBmb3IgdGhlIG5vdGVzIHlvdSBjYW5ub3QgY2hhbmdlLCB3aGlsZSBuZWdhdGl2ZSBpbnRlZ2VycyBhcmUgd2hhdCB5b3UgY2FuIHJlcGxhY2Ugd2l0aCBhcmJpdHJhcnkKIG5vdGVzLiBUaGUgbm90ZXMgYXJlIG5hbWVkIGZyb20gMSB0byBtLgogCjxicj4KT3V0cHV0CkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0IHRoZSBhbnN3ZXIgaW4gb25lIGxpbmUuCiAKPGJyPgpTYW1wbGUgSW5wdXQKCjxwcmUgY2xhc3M9"brush:java;">2 5 3 83 86 77 15 93 35 86 92 49 3 3 3 1 2 10 5 36 11 68 67 29 82 30 62 23 67 35 29 2 22 58 69 67 93 56 11 42 29 73 21 19 -1 -1 5 -1 4 -1 -1 -1 4 -1
Sample Output
270 625
题意：（引用别人的解释）
题意为有m种音符，编号1到m，我们要用这m种音符来创造一首带有n个音符的曲子（当然，一种音符可以用多次）,假设有两个连续的音符 i ,j ，那么定义score(i,j)为这两个音符的得分，题目中预先给出所有的score(i,j) 1<=i,j<=m, 那么我们创造出的n个音符的曲子的得分为 score( note[i] , note[i+1] ) + score (note[i+1] ,note[i+2) +......score(note[n-1],note[n]) ， i从1开始。 note [i] 代表n个音符的曲子中第i个音符是第几种音符， 1<=note[i]<=m， 比如 note[i]=3，就表示n个音符中第i个位置用的是第3种音符（一共有m种）,预先给出 这n个音符，note[1] 到note[n] ，其中note[ i] 或者等于-1 ，或者 大于等于1小于等于m，对于后者，该位置的音符不能改变，对于前者，该位置可以换成任意的音符j(1<=j<=m)， 问 这n个音符所获得的最大得分是多少。
解释在代码中，这里我贴出来一个对的和一个有bug的代码：
对的代码：
#include#include #include #include #include #include #include #include #define L(x) (x<<1) #define R(x) (x<<1|1) #define MID(x,y) ((x+y)>>1) #define eps 1e-8 using namespace std; #define N 105 int b[N][N],a[N]; int n,m; int dp[N][N]; //dp[i][j]表示长度为i,以j结尾的最大价值 void solve() { int i,j,k; memset(dp,0,sizeof(dp)); for(i=2;i<=n;i++) if(a[i]<0) { if(a[i-1]<0) { 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 { for(k=1;k<=m;k++) dp[i][k]=max(dp[i][k],dp[i-1][a[i-1]]+b[a[i-1]][k]); } } 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; }
有bug代码：
#include#include #include #include #include #include #include #include #define L(x) (x<<1) #define R(x) (x<<1|1) #define MID(x,y) ((x+y)>>1) #define ep