CF#508 1038E Maximum Matching

～～～题面～～～

题解：

　　感觉还是比较妙的，复杂度看上去很高（其实也很高），但是因为n只有100，所以还是可以过的。

　　考虑一个很暴力的状态f[i][j][x][y]表示考虑取区间i ~ j的方格，左右端点颜色分别是x, y.的最大值。

　　那么有如下转移

　　1,直接继承子区间的答案

　　　　f[i][j][x][y] = max(f[i][k][x][y], f[k + 1][j][x][y]);//因为子区间就这2种，毕竟子区间一定比当前区间小，因此不靠在端点上的区间一定已经被靠在端点上的区间给取过max了。

　　2，由2段子区间拼凑而来，相当于枚举中间断开的地方是选了那个块.//如果中间断开的地方的块没有被选，那么一定可以找到一个被选的块作为断点(如果找不到就说明这整个区间内只取了端点，再转移也没有什么意义。)

　　　　翻转操作是不需要考虑的，因为可以在初始化的地方就处理掉，因此只需要在转移的地方考虑一下乱序继承即可。

　　　　即正常的顺序是[i, l] + [l + 1, j] = [i, j];

　　　　乱序则可以支持[l + 1][j] + [i, l] = [i, j];

　　　　所以对于这2种情况都转移一下，转移的时候必须要求相接的地方颜色相同即可。

　　注意因为有子区间相加转移的地方，所以初始化为极小值的时候不要太小了，不然太小了直接一加就爆了。

 #include<bits/stdc++.h>

 using namespace std;

 #define R register int

 #define AC 110

 #define ac 6

 int n, ans;

 int f[AC][AC][ac][ac];

 inline int read()

 {

     int x = ;char c = getchar();

     while(c > '' || c < '') c = getchar();

     while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

     return x;

 }

 void pre()

 {

     n = read();

     memset(f, -, sizeof(f));

     int a, b, c;

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

     {

         a = read(), b = read(), c = read();

         f[i][i][a][c] = f[i][i][c][a] = b;

     }

 }

 inline void upmax(int &a, int b)

 {

     if(b > a) a = b;

 }

 void work()

 {

     for(R i = n; i; i --)

         for(R j = i; j <= n; j ++)

             for(R x = ; x <= ; x ++)

                 for(R y = ; y <= ; y ++)

                 {

                     for(R l = i; l < j; l ++)

                     {

                         upmax(f[i][j][x][y], max(f[i][l][x][y], f[l + ][j][x][y]));

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

                         {

                             upmax(f[i][j][x][y], f[i][l][x][k] + f[l + ][j][k][y]);

                             upmax(f[i][j][x][y], f[i][l][k][y] + f[l + ][j][x][k]);

                         }

                     }

                     upmax(ans, f[i][j][x][y]);

                 }

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

 }

 int main()

 {

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

     pre();

     work();

     //fclose(stdin);

     return ;

 }

巴特西

CF#508 1038E Maximum Matching

最新文章

热门文章