• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

P1541 [NOIP2010 提高组] 乌龟棋 解题报告

开发技术 开发技术 2周前 (04-08) 8次浏览

原题链接

考察:线性dp

思路:

        一开始的思路是定义结构体dp数组,但是会出现到达同一点剩余卡片种类不同的情况,只要卡片种类不同就会获得不同的分数,所以必须记录剩余卡片种类.

       考虑到M很小,cnt(每种卡片)<=40.可以考虑开数组f[i][j][k][p][q] 表示到i点时剩余卡片为j,k,p,q的最大分.但是注意到i是不必要的,因为可以根据还剩多少卡片来推得目前位置.由此可压成四维.

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 const int N = 350,M = 41;
 5 int n,m,s[N],cnt[5],f[M][M][M][M];
 6 int get(int a,int b,int c,int d)
 7 {
 8     int now = 1+cnt[1]-a+(cnt[2]-b)*2+(cnt[3]-c)*3+(cnt[4]-d)*4;
 9     return now; 
10 }
11 void solve()
12 {
13     f[cnt[1]][cnt[2]][cnt[3]][cnt[4]] = s[1];
14     //for(int i=1;i<=n;i++)
15       for(int j=cnt[1];j>=0;j--)
16         for(int k=cnt[2];k>=0;k--)
17           for(int t=cnt[3];t>=0;t--)
18             for(int p=cnt[4];p>=0;p--)
19             {
20                 int v = f[j][k][t][p];
21                 int i = get(j,k,t,p);
22                 int& a = f[j-1][k][t][p];
23                 int& b = f[j][k-1][t][p];
24                 int& c = f[j][k][t-1][p];
25                 int& d = f[j][k][t][p-1];
26                 if(j-1>=0) a = max(v+s[i+1],a);
27                 if(k-1>=0) b = max(v+s[i+2],b);
28                 if(t-1>=0) c = max(v+s[i+3],c);
29                 if(p-1>=0) d = max(v+s[i+4],d);
30             }
31 }
32 int main()
33 {
34     scanf("%d%d",&n,&m);
35     for(int i=1;i<=n;i++) scanf("%d",&s[i]);
36     for(int i=1;i<=m;i++)
37     {
38         int x; scanf("%d",&x);
39         cnt[x]++;
40     }
41     solve();
42     printf("%dn",f[0][0][0][0]);
43     return 0;
44 }

 


程序员灯塔
转载请注明原文链接:P1541 [NOIP2010 提高组] 乌龟棋 解题报告
喜欢 (0)