BZOJ4831: [Lydsy1704月赛]序列操作（非常nice的DP& 贪心）

4831: [Lydsy1704月赛]序列操作

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 250 Solved: 93
[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

思路：求最大值肯定就是直接贪心就好了。

难点在于求最小值，我们用dp[i]表示i前面满足没有相邻的非0值，而且把i取掉的最小代价，开始我想通过相邻两项来得到dp公式，发现有后效性，很难dp。

然后我们考虑前面三项，就没有后效性了。

rep(i,3,N)    dp[i]=min(dp[i-2]+a[i],dp[i-3]+max(a[i-1],a[i]));

如上，不难看出是对的。就是有点难想到，ORZ。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=100010;
int dp[maxn],a[maxn];
void read(int &x){
    x=0; char c=getchar();
    while(c>'9'||c<'0') c=getchar();
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
}
int main()
{
    int T,N,ans;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&N);  ans=0;
        rep(i,1,N) read(a[i]);
        dp[1]=a[1]; dp[2]=a[2];
        rep(i,3,N)
         dp[i]=min(dp[i-2]+a[i],dp[i-3]+max(a[i-1],a[i]));
        rep(i,2,N) {
            int tmp=min(a[i-1],a[i]);
            a[i]-=tmp; ans+=tmp;
        }
        printf("%d %d
",min(dp[N],dp[N-1]),ans);
    }
    return 0;
}