程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 5074 Hatsune Miku(簡單二維dp)

HDU 5074 Hatsune Miku(簡單二維dp)

編輯：C++入門知識

HDU 5074 Hatsune Miku(簡單二維dp)

題目大意：給你一些音符之間的聯系，給你一個串，讓你求出這個串的最大值。-1的時候可以任意替代，其他情況必須為序列上的數。

解題思路：簡單二維dp，分情況處理就可以了啊。

Hatsune Miku

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

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

Source 2014 Asia AnShan Regional Contest

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define eps 1e-9
///#define M 1000100
///#define LL __int64
#define LL long long
///#define INF 0x7ffffff
#define INF 0x3f3f3f3f
#define PI 3.1415926535898
#define zero(x) ((fabs(x)>T;
    while(T--)
    {
        int n, m;
        scanf("%d %d",&m, &n);
        for(int i = 1; i <= 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<