【动态规划去除冗余】NOIP2010-乌龟棋

【题目大意】

【思路】

最简单的思路是五维数组，但是当前走到的步数由已经取到的卡片决定，所以只需要四维。本来想要改一个滚动数组的，但是好像没有滚起来，算了(ノ｀Д)ノ。

在学校要晚自习到21:15，回到家大概就22:00了，本来每天晚上想要切题的但是想到第二天五点多又要起床了，算了orz在努力问老师讨机房钥匙，虽然并没有成功。

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 using namespace std;

 const int MAXN=+;

 const int MAXM=+;

 int n,m;//棋子的数量和卡片的数量

 int a[MAXN];//每一格的分数

 int num[];

 int f[MAXM][MAXM][MAXM][MAXM];//四张卡片分别取这四张时候的最多得分

 int main()

 {

     //freopen("tortoise1.in","r",stdin);

     scanf("%d%d",&n,&m);

     for (int i=;i<n;i++) scanf("%d",&a[i]);

     /*因为起点是第一个格子，所以下标从零开始设*/

     for (int i=;i<m;i++)

     {

         int t;

         scanf("%d",&t);

         num[t-]++;

     }

     cout<<num[]<<endl;

     memset(f,,sizeof(f));

     for (int i1=;i1<=num[];i1++)

         for (int i2=;i2<=num[];i2++)

             for (int i3=;i3<=num[];i3++)

                 for (int i4=;i4<=num[];i4++)

                 {

                     int score=a[i1+i2*+i3*+i4*];

                     f[i1][i2][i3][i4]=;

                     if (i1>) f[i1][i2][i3][i4]=max(f[i1-][i2][i3][i4],f[i1][i2][i3][i4]);

                     if (i2>) f[i1][i2][i3][i4]=max(f[i1][i2-][i3][i4],f[i1][i2][i3][i4]);

                     if (i3>) f[i1][i2][i3][i4]=max(f[i1][i2][i3-][i4],f[i1][i2][i3][i4]);

                     if (i4>) f[i1][i2][i3][i4]=max(f[i1][i2][i3][i4-],f[i1][i2][i3][i4]);

                     f[i1][i2][i3][i4]+=score;

                 }

     cout<<f[num[]][num[]][num[]][num[]]<<endl;

          return ;

 }