2020.3.21

P1569 Generic Cow Protests

简单题意：

给定 \(n(n≤1000)\)个数，要求分成几组（必须连续），使得每一组之和，求最多能分成多少段。
如果无解输出"Impossible"

思路：

前缀和思想，令 \(sum[i]\)表示第 \(1\)个数到第 \(i\)个数之和，\(f[i]\)表示前 \(i\)个数最多分组
如果前 \(i\)个数之和 \(≥0\)，那么前 \(i\)个肯定至少有一组了，\(f[i]=1\)
如果 \(j<i\)并且 \(j到i\)之和 \(≥0\)，前 \(j\)个数至少可分一组，则 \(j到i\)可以成为一组了
转移方程便是：

\(f[i]=max(f[i],f[j]+1)\)，其中\(j<=i\)且\(f[j]!=0\)

code:

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;
const int N=1005; 
int a[N],sum[N],n,f[N]; 
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
        if(sum[i]>=0)//如果前缀和大于0，至少有一组
        f[i]=1; 
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)//j到i-1即可，因为j<i
        {
            if(f[j]&&sum[i]-sum[j]>=0)
            {
                f[i]=max(f[j]+1,f[i]);
            }
        }
    }
    if(f[n]>0)//如果可以分组
    cout<<f[n];
    else//否则
    cout<<"Impossible";//输出"Impossible"，不看题的教训 
    return 0;
}