HDU 5074 Hatsune Miku（dp）
Problem Description
Hatsune Miku is a popular virtual singer. It is very popular in both Japan and China. Basically it is a computer software that allows you to compose a song on your own using the vocal package.
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 evaluate the beautifulness of a song. FZ喎?http://www.Bkjia.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 eps 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;
}
