程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 5074-Hatsune Miku（DP）

HDU 5074-Hatsune Miku（DP）

編輯：C++入門知識

HDU 5074-Hatsune Miku（DP）

Hatsune Miku

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 29 Accepted Submission(s): 25

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+Ck5vdywgeW91IGZpbmQgdGhhdCBhdCBzb21lIHBvc2l0aW9ucywgdGhlIG5vdGVzIGhhdmUgdG8gYmUgc29tZSBzcGVjaWZpYyBvbmVzLCBidXQgYXQgb3RoZXIgcG9zaXRpb25zIHlvdSBjYW4gZGVjaWRlIHdoYXQgbm90ZXMgdG8gdXNlLiBZb3Ugd2FudCB0byBtYXhpbWl6ZSB5b3VyIHNvbmehr3MgYmVhdXRpZnVsbmVzcy4gV2hhdCBpcyB0aGUgbWF4aW11bSBiZWF1dGlmdWxuZXNzIHlvdSBjYW4gYWNoaWV2ZT8KCiAKPGJyPgoKSW5wdXQKClRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgVCAoVCCh3CAxMCksIGRlbm90aW5nIHRoZSBudW1iZXIgb2YgdGhlIHRlc3QgY2FzZXMuPGJyPgo8YnI+CkZvciBlYWNoIHRlc3QgY2FzZSwgdGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzIG4oMSCh3CBuIKHcIDEwMCkgYW5kIG0oMSCh3CBtIKHcIDUwKSBhcyBtZW50aW9uZWQgYWJvdmUuIFRoZW4gbSBsaW5lcyBmb2xsb3csIGVhY2ggb2YgdGhlbSBjb25zaXN0aW5nIG9mIG0gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzLCB0aGUgai10aCBpbnRlZ2VyIGluIHRoZSBpLXRoIGxpbmUgZm9yIHNjb3JlKGksIGopKCAwIKHcIHNjb3JlKGksIGopIKHcIDEwMCkuCiBUaGUgbmV4dCBsaW5lIGNvbnRhaW5zIG4gaW50ZWdlcnMsIGE8c3ViPjE8L3N1Yj4sIGE8c3ViPjI8L3N1Yj4sIC4gLiAuICwgYTxzdWI+bjwvc3ViPiAoLTEgodwgYTxzdWI+aTwvc3ViPiCh3CBtLCBhPHN1Yj5pPC9zdWI+IKHZIDApLCB3aGVyZSBwb3NpdGl2ZSBpbnRlZ2VycyBzdGFuZCBmb3IgdGhlIG5vdGVzIHlvdSBjYW5ub3QgY2hhbmdlLCB3aGlsZSBuZWdhdGl2ZSBpbnRlZ2VycyBhcmUgd2hhdCB5b3UgY2FuIHJlcGxhY2Ugd2l0aCBhcmJpdHJhcnkKIG5vdGVzLiBUaGUgbm90ZXMgYXJlIG5hbWVkIGZyb20gMSB0byBtLgoKIAo8YnI+CgpPdXRwdXQKCkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0IHRoZSBhbnN3ZXIgaW4gb25lIGxpbmUuCgogCjxicj4KClNhbXBsZSBJbnB1dAoKPHByZSBjbGFzcz0="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鞍山現場賽的第二道水題，。。設狀態dp[i][k]表示第i個位置放編號為k的物品，則dp[i][k]=max(dp[i][k],dp[i-1][j]+dis[j][k])枚舉第i-1為位置上放置的物品。#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ll long long
using namespace std;
const int INF=0x3f3f3f3f;
int n,m,dis[55][55],a[110],dp[110][55];
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		memset(dp,-1,sizeof(dp));
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;i++)
			for(int j=1;j<=m;j++)
			scanf("%d",&dis[i][j]);
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]);
		if(a[1]!=-1)
			dp[1][a[1]]=0;
		else
			for(int i=1;i<=m;i++)
			dp[1][i]=0;
		for(int i=2;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				if(dp[i-1][j]!=-1)
				{

					if(a[i]!=-1)
						dp[i][a[i]]=max(dp[i][a[i]],dp[i-1][j]+dis[j][a[i]]);
					else
						for(int k=1;k<=m;k++)
						dp[i][k]=max(dp[i][k],dp[i-1][j]+dis[j][k]);
				}
			}
		}
		int ans=-INF;
		for(int i=1;i<=m;i++)
			ans=max(ans,dp[n][i]);
		printf("%d\n",ans);

	}
    return 0;
}