P2389 电脑班的裁员 (动态规划)

题目背景

隔壁的新初一电脑班刚考过一场试，又到了BlingBling的裁员时间，老师把这项工作交给了ZZY来进行。而ZZY最近忙着刷题，就把这重要的任务交（tui）给了你。

题目描述

ZZY有独特的裁员技巧：每个同学都有一个考试得分ai（-1000<=ai<=1000），在n个同学（n<=500）中选出不大于k段（k<=n）相邻的同学留下，裁掉未被选中的同学，使剩下同学的得分和最大。要特别注意的是，这次考试答错要扣分【不要问我为什么】，所以得分有可能为负。

输入输出格式

输入格式：

第一行为n，k，第二行为第1~n位同学的得分。

输出格式：

一个数s，为最大得分和。

输入输出样例

输入样例#1：

5 3

1 -1 1 -1 1

输出样例#1：

说明

2014彭鲲志：“题目这么短一看就很水。”

Solution

这个题我一开始想用贪心做,结果发现,只有20分.

我的贪心思路是:

把所有正区间,和负区间都合并起来.

然后按和的大小排序.然后取m个.

很显然我是个** ,很明显还有更多正区间可能可以联上的没处理.

其实正解里面有贪心.

贪心:

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

int n,m,c[maxn];

struct sj{

    int w;

    int id;

}t[maxn];

int num,ans;

void pre()

{

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

    {

        int flag=,now=c[i];

        if(c[i]<)

        {

            while(c[i+flag]<)

            {now+=c[i+flag];flag++;}

            t[++num].w=now;

            t[num].id=num;

            i+=(flag);continue;

        }

        if(c[i]>=)

        {

            while(c[i+flag]>=&&i+flag<=n)

            {now+=c[i+flag];flag++;}

            t[++num].w=now;

            t[num].id=num;

            i+=(flag);continue;

        }

    }

}

bool cmp(sj s,sj j){return s.w>j.w;}

int main()

{

    scanf("%d%d",&n,&m);

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

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

    pre();

    sort(t+,t+num+,cmp);

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

    ans+=t[i].w;

    cout<<ans<<endl;

}

然后就去想DP,很好想.

状态定义:

　　$f[ i ] [ j ]$ 表示当前到 $i$ 这个点,已经选了 $j$ 个区间.

转移方程也很好想:

$ f [ i ] [ j ] = max ( f[ i ] [ j ] , f[ k ] [ j-1 ]+ sum( k-->i ) );$

时间复杂度 O(n^3).

不过有 O(n^2) ?

DP

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

int n,m,c[maxn];

int sum[maxn];

int f[maxn][maxn];

int main()

{

    scanf("%d%d",&n,&m);

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

    scanf("%d",&c[i]),sum[i]=sum[i-]+c[i];

    f[][]=c[];

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

    for(int j=;j<=m;j++)

    {

        f[i][j]=f[i-][j];

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

        f[i][j]=max(f[i][j],f[k][j-]+sum[i]-sum[k]);

    }

    cout<<f[n][m]<<endl;

}

巴特西