51nod1254 最大子段和 V2 DP

～～～题面～～～

题解：

　　表示今天做题一点都不顺。。。。

　　这题也是看了题解思路然后自己想转移的。

　　看的题解其实不是这道题，但是是这道题的加强版，因为那道题允许交换k对数。

　　因为我们选出的是连续的一段，所以假设我们选了某一段，那么原序列将会被分为3段，我们设这3段分别是第0段，第1段和第2段，我们假设我们选出的区间是第1段。

　　那么我们的目的就是要从第0段或第2段中选出一个数，从第1段中剔除一个数，使得1段中剩余数+选出数之和最大。　　

　　所以我们设f[i][j][k][l]表示DP到i位，已经选出了j个数，剔除了k个数，当前在第l段的最大值。

　　那么每次转移的时候就枚举一下当前的状态，如果当前在第0段or第2段，那么就考虑选出一个数or不选一个数。

　　如果当前在第1段，那么就考虑剔除这个数or保留这个数。

　　最后的答案就枚举一下最后一个数是属于哪一段，是否有交换（如果交换就是选出1个数，剔除1个数）。

　　这里虽然强制交换，但和可以选择交换不交换是等效的。

　　因为当n <= 2的时候，交换显然无意义。当n > 2的时候，属于1段的数的个数和不属于1段的数的个数中肯定有一个>= 2，那么交换一个段内部的数肯定是不会产生影响的，所以和不交换一样。

　　因此选择不交换一定是合法的。

 #include<bits/stdc++.h>

 using namespace std;

 #define R register int

 #define AC 50100

 #define LL long long

 int n;

 int s[AC];

 LL f[AC][][][];//DP到i位， 选出j个，剔除k个，当前在第l段的最大值。

 inline int read()

 {

     int x = ;char c = getchar();bool z = false;

     while(c > '' || c < '')

     {

         if(c == '-') z = true;

         c = getchar();

     }

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

     if(!z) return x;

     else return -x;

 }

 void pre()

 {

     n = read();

     for(R i = ; i <= n; i ++) s[i] = read();

 }

 LL Max(LL a, LL b, LL c)

 {

     if(a > b && a > c) return a;

     else if(b > c) return b;

     else return c;

 }

 LL Max_(LL a, LL b, LL c, LL d)

 {

     if(a > b && a > c && a > d) return a;

     else if(b > c && b > d) return b;

     else if(c > d) return c;

     else return d;

 }

 void work()

 {

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

     {

          f[i][][][] = max(f[i - ][][][], f[i - ][][][] + s[i]);

          f[i][][][] = max(f[i - ][][][], f[i - ][][][]) + s[i];

          f[i][][][] = Max(f[i - ][][][], f[i - ][][][] + s[i], f[i - ][][][]);

          f[i][][][] = max(f[i - ][][][], f[i - ][][][]) + s[i];

          f[i][][][] = Max(f[i - ][][][] + s[i], f[i - ][][][], f[i - ][][][]);

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

          f[i][][][] = Max_(f[i - ][][][], f[i - ][][][], f[i - ][][][] + s[i], f[i - ][][][] + s[i]);

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

     }

     printf("%lld\n", Max_(f[n][][][], f[n][][][], f[n][][][], f[n][][][]));

 }

 int main()

 {

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

     pre();

     work();

     fclose(stdin);

     return ;

 }

巴特西

51nod1254 最大子段和 V2 DP

最新文章

热门文章