Codeforces Flipping game 动态规划基础

时间：2022-10-09 15:57:27

题目链接：http://codeforces.com/problemset/problem/327/A

这道题目有O(N^3)的做法，这里转化为动态规划求解，复杂度是O(N)

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <cmath>

 #include <cctype>

 #include <algorithm>

 #include <queue>

 #include <set>

 #include <queue>

 #include <list>

 #include <map>

 using namespace std;

 #define INF 0x3f3f3f3f

 int a[], b[], c[];

 int main ( void )

 {

     int n, n1=, cnt=;

     while (~scanf("%d", &n))

     {

         n1 = cnt = ;

         memset(a, , sizeof(a));

         memset(b, , sizeof(b));

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

             scanf("%d",a+i); if(a[i]) n1++;

             if (a[i]) b[i]=-; else b[i]=;

         }

         c[] = ;

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

         {

             c[i] = c[i-] + b[i];

         }

         int Max = -INF, Min = c[];

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

             if (c[i] - Min > Max) Max = c[i]-Min;

             if (c[i] < Min) Min = c[i];

         }

         printf("%d\n",n1+Max);

     }

         return ;

 }

转化为子序列的最大连续和

相关文章