bzoj 4831 [Lydsy1704月赛]序列操作 dp

[Lydsy1704月赛]序列操作

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 203 Solved: 69
[Submit][Status][Discuss]

Description

给定一个长度为 n 的非负整数序列 a_1,a_2,...a_n 。你可以使用一种操作：选择在序列中连续的两个正整数，

并使它们分别减一。当你不能继续操作时游戏结束，而你的得分等于你使用的操作次数。你的任务是计算可能的最小

得分和最大得分。

Input

第一行包含一个正整数 T ，表示有 T 组数据，满足 T ≤ 200 。

接下来依次给出每组测试数据。对于每组测试数据：

第一行包含一个正整数 n ，满足 1 ≤ n ≤ 10^5 。

第二行包含 n 个非负整数，表示 a_1,a_2,...a_n ，满足 Σa_i ≤ 10^6 。

约 5 组数据满足 n ≥ 10^3 或 Σa_i ≥ 10^4 。

Output

对于每组测试数据

输出一行两个非负整数，用一个空格隔开，前者表示可能的最小得分，后者表示可能的最大得分。

Sample Input

2
4
1 2 1 3
5
1 2 1 1 3

Sample Output

2 2
2 3

HINT

 #include<queue>

 #include<vector>

 #include<cstdio>

 #include<string>

 #include<cstring>

 #include<cstdlib>

 #include<algorithm>

 using namespace std;

 int f[][],F[][];

 int g[][],G[][];

 int a[];

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T>)

     {

         T--;

         int n;

         scanf("%d",&n);

         int i,j;

         int lim=;

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

         {

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

             lim=max(lim,a[i]);

         }

         if(n==)

         {

             printf("0 0\n");

             continue;

         }

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

         {

             f[][j]=-;

             F[][j]=-;

             g[][j]=;

             G[][j]=;

             f[][j]=-;

             F[][j]=-;

             g[][j]=;

             G[][j]=;

         }

         int p=,q=;

         int tmp=min(a[],a[]);

         for(i=;i<tmp;i++)

             F[p][a[]-i]=G[p][a[]-i]=i;

         f[p][a[]-tmp]=tmp;

         g[p][a[]-tmp]=tmp;

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

         {

             for(j=;j<=a[i];j++)

             {

                 f[q][j]=max(f[p][a[i]-j],F[p][a[i]-j])+a[i]-j;

                 g[q][j]=min(g[p][a[i]-j],G[p][a[i]-j])+a[i]-j;

             }

             for(j=a[i];j<=a[i-];j++)

             {

                 f[q][]=max(f[q][],f[p][j]+a[i]);

                 g[q][]=min(g[q][],g[p][j]+a[i]);

             }

             f[q][]=max(f[q][],F[p][a[i]]+a[i]);

             g[q][]=min(g[q][],G[p][a[i]]+a[i]);

             for(j=a[i-]-;j>=;j--)

             {

                 f[p][j]=max(f[p][j],f[p][j+]);

                 g[p][j]=min(g[p][j],g[p][j+]);

             }

             for(j=;j<=a[i];j++)

             {

                 F[q][j]=max(f[p][a[i]-j],F[p][a[i]-j])+a[i]-j;

                 G[q][j]=min(g[p][a[i]-j],G[p][a[i]-j])+a[i]-j;

             }

             for(j=;j<=a[i-];j++)

             {

                 f[p][j]=-;

                 F[p][j]=-;

                 g[p][j]=;

                 G[p][j]=;

             }

             p=-p;

             q=-q;

         }

         int ansmax=-,ansmin=;

         for(i=;i<=a[n];i++)

         {

             ansmax=max(ansmax,f[p][i]);

             ansmin=min(ansmin,g[p][i]);

         }

         printf("%d %d\n",ansmin,ansmax);

     }

 }

巴特西