CDQZ集训DAY10 日记

　　又一次跪了，跪在了神奇的数据范围上。

　　T1上来打完暴力之后觉得是数据结构题，像三维偏序，于是开始往各种数据结构上想，主席树，线段树+calc，平衡树，树套树，CDQ……最终在经过一番思考之后选择去打CDQ，打完之后自己拍了一下，发现我的想法是错的，考虑了一下转场。T2好像又是原题，打完暴力之后开始回忆，只记得答案和期望无关，XYZ讲过，卡区间去做，然而细节记不住了。T3一开始还以为是子串，觉得还挺容易，结果一看是子序列，打完暴力就跪了。纠结了一下去打T1，又用了半个小时打了一整套线段树套SPLAY，打完调完发现也行不通，痛苦ing……最后憋住劲查出来了vector没调库……

　　下午发现分少的可怜，T1暴力65分，我虽然打了，但是由于我当时不知道该不该放那个CDQ的错解骗分，只将暴力限定在了2000以内，然而题目描述里小于2000的只有30分啊，虽然常数小但是没这么坑人的啊！

　　讲课仍然不错，听的还是挺明白的，除了四边形不等式优化。

　　晚上接着打插头DP，然而感到了收杀头DP支配的恐惧……一晚上打一道插头DP都没调完。话说3进制到底怎么玩？？

 #include<iostream>

 #include<cmath>

 #include<vector>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<algorithm>

 #define N 9

 #define M 105

 using namespace std;

 int n,m;

 int ma[M][M],b[M];

 int f[M][N][];

 int zt[][],xp[M];

 int main()

 {

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

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

     {

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

         {

             scanf("%d",&ma[i][j]);

         }

     }

     xp[]=;

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

     {

         xp[i]=xp[i-]*;

     }

     for(int i=;i<xp[m+];i++) b[i]=i%;

     int ans=-0x7fffffff;

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

     {

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

         {

             int x=xp[j-],y=xp[j];

             for(int k=;k<xp[m+];k++)

             {

                 int p=b[k/x],q=b[k/y],t=k-x*p-y*q;

                 if(!p&&!q)

                 {

                     f[i][j][k]=max(f[i][j-][k],f[i][j][k]);

                     f[i][j][k+x+(y<<)]=max(f[i][j][k+x+(y<<)],f[i][j-][k]+ma[i][j]);

                 }

                 else if((!p&&q==)||(!q&&p==))

                 {

                     f[i][j][t+x]=max(f[i][j][t+x],f[i][j-][k]+ma[i][j]);

                     f[i][j][t+y]=max(f[i][j][t+y],f[i][j-][k]+ma[i][j]);

                 }

                 else if((!p&&q==)||(!q&&p==))

                 {

                     f[i][j][t+(x<<)]=max(f[i][j][t+(x<<)],f[i][j-][k]+ma[i][j]);

                     f[i][j][t+(y<<)]=max(f[i][j][t+(y<<)],f[i][j-][k]+ma[i][j]);

                 }

                 else if(p==&&q==&&!t&&ans<f[i][j-][k]+ma[i][j]) ans=f[i][j-][k]+ma[i][j],cout<<i<<' '<<j<<' '<<ans<<endl;

                 else if(p==&&q==) f[i][j][t]=max(f[i][j][t],f[i][j-][k]+ma[i][j]);

                 else if(p==&&q==)

                 {

                     int u,tmp;

                     for(tmp=,u=j+;u<=m&&tmp>=;tmp+=(b[t/xp[u]]==)-(b[t/xp[u]]==),u++);

                     u--;

                     f[i][j][t-xp[u]]=max(f[i][j][t-xp[u]],f[i][j-][k]+ma[i][j]);

                 }

                 else if(p==&&q==)

                 {

                     int u,tmp;

                     for(tmp=,u=j-;u>=&&tmp>=;tmp+=(b[t/xp[u]]==)-(b[t/xp[u]]==),u--);

                     u++;

                     f[i][j][t+xp[u]]=max(f[i][j][t+xp[u]],f[i][j-][k]+ma[i][j]);

                 }

             }

         }

         for(int j=;j<xp[m];j++) if(b[j]==)f[i+][][j/]=f[i][m][j];

     }

     printf("%d\n",ans);

     return ;

 }

存一个代码

巴特西

CDQZ集训DAY10 日记

最新文章

热门文章