[NOI2009]管道取珠 DP + 递推

～～～题面～～～

思路：

主要难点在思路的转化，

不能看见要求$\sum{a[i]^2}$就想着求a[i]，

我们可以对其进行某种意义上的拆分，即a[i]实际上可以代表什么？

假设我们现在有两种取出某一数列的方法，分别为X，Y。（X,Y可以相同）

那么这样的二元组有多少个呢？

a[i]^2个。

因为X的取法有a[i]种，Y的取法也是a[i]种，所以二元组个数实际上就是a[i]^2.

那么这样一转化有什么好处？

方便DP

因为这样的话就不在需要知道具体的a[i]了，因为二元组的个数是可以拆开来算的，

所以就可以考虑递推/DP了。

我们用f[i][j][k][l]表示第一种决策X在上面取了i个，下面取了j个，第二种决策Y在上面取了k个，在下面取了l个且产生序列相同的二元组个数

显然一开始的f[0][0][0][0]要设为1，

然后注意到我们应该要同步取，不然个数都不同，序列也不可能相同了，

因此我们数组中就可只存3维了，因为第4维可以通过i + j - k得到。

那么应该如何转移呢？

假设现在我们有f[i][j][k]，显然要使下一次取出来的序列相同，只要让下一次取的珠子一样就可以了，因为其他部分现在已经一样了，

因此我们就可以分别枚举X取上面，X取下面，Y取上面，Y取下面，然后相互搭配，一共4种情况，如果满足下一次取的珠子一样就可以转移，

因为n有500，所以空间还是承受不了，观察到i的转移只涉及到i和i+1，因此我们可以用滚动数组优化。

但是我们注意到用f[i][j][k]向f[i+1][j][k+1]这类的转移的话，如果不及时清空，因为使用的是滚动数组，转移的时候又是+=，无法将原来的答案覆盖，

那就会重复统计，因此我们不能向前转移，我们应该要枚举当前状态，枚举向当前状态转移的状态，并且每次转移之前要清空数组，这样就可以了

注意将不合法的状态减掉，luogu上这题貌似有点卡常，，，

work1是另一种状态表示方法，，，我也不知道为什么比work快

 #include<bits/stdc++.h>

 using namespace std;

 #define R register int

 #define AC 510

 #define mod 1024523

 /*转化为有序数对的统计之后就可以不用在意具体数列到底是什么样的了，因为只要相同就可以了,

 但是由于是同步取的，所以两种决策取的次数是相同的，所以少掉一维是没关系的，

 因为剩下那维可以直接推出来,是没用的*/

 int n,m,now;

 int f[][AC][AC];

 char U[AC],D[AC];

 void pre()

 {

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

     scanf("%s", U + );

     scanf("%s", D + );

     reverse(U+,U+n+);

     reverse(D+,D+m+);//因为是从右边开始取的，所以要反过来！！！

 }

 inline void update(int &a,int b)

 {

     a += b;

     if(a > mod) a -= mod;

 }

 //本来是向前做贡献，但是这样贡献会和前面的累加，

 //所以需要在做的过程中初始化，但这样就不太好掌控什么时候初始化，

 //因此改成从前面取贡献，方便初始化,但是这样的话前面的判断就要麻烦点了

 void work()

 {

     f[now][][] = ;//一开始啥也没取，，，

     for(R i=;i<=n;i++)//可以取0个啊

     {

         for(R j=;j<=m;j++)

             for(R k=;k<=n;k++)

             {

                 if(!i && !j) continue;//这个不能初始化掉了

                 if(i + j - k > m) continue;//因为i,j,k枚举了，所以肯定合法，但最后一个要计算得到，不一定合法

                 f[now][j][k] = ;//初始化，防止叠加

                 if(i && k && U[i] == U[k]) update(f[now][j][k],f[now^][j][k-]);

                 if(i && i + j - k && U[i] == D[i + j - k]) update(f[now][j][k],f[now^][j][k]);

                 if(j && k && D[j] == U[k]) update(f[now][j][k],f[now][j-][k-]);

                 if(j && i + j - k && D[j] == D[i + j - k]) update(f[now][j][k],f[now][j-][k]);

             //    printf("%d %d %d = %d\n",i,j,k,f[now][j][k]);

             }

         now ^= ;

     }

     printf("%d\n",f[now^][m][n]);

     printf("time used ... %lf\n",(double)clock()/CLOCKS_PER_SEC);

 }

 void work1()

 {//现在取了i个，第一种决策在第一行取了j个，第二种取了k个

     f[][][] = ;//因为是滚了一维

     int b = n + m;

     for(R i = ; i <= b; i++)

     {

         int lim = min(i, n);

         for(R j = ; j <= lim; j++)

         {

             for(R k = ; k <= lim; k++)

             {

                 int x = i - j, y = i - k;//x为第一种决策在第二行取的，y则是第二种决策

                 if(x > m || y > m) continue;

                 f[now][j][k] = ;

                 if(j && U[j] == U[k]) update(f[now][j][k], f[now^][j-][k-]);

                 if(j && U[j] == D[y]) update(f[now][j][k], f[now^][j-][k]);

                 if(x && D[x] == U[k]) update(f[now][j][k], f[now^][j][k-]);

                 if(x && D[x] == D[y]) update(f[now][j][k], f[now^][j][k]);

         //        printf("%d %d %d = %d\n",i,j,k,f[now][j][k]);

             }

         }

         now ^= ;

     }

     printf("%d\n",f[now^][n][n]);

 //    printf("time used ... %lf\n",(double)clock()/CLOCKS_PER_SEC);

 }

 int main()

 {

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

     pre();

     //work();

     work1();

     //fclose(stdin);

     return ;

 }

巴特西

[NOI2009]管道取珠 DP + 递推

最新文章

热门文章