Dark`Kris

Private blog

I'm spark , hope you fire


Luogu P1569 KC与龙珠 解题报告

不费话了,直接切入正题。下面看一下题目

题目背景

KC与龙珠

题目描述

ZKC大神和LSH大神省队集训时住在同一个房间,他们有时候会一起去楼下的85℃喝奶茶,同时在电脑上玩《龙珠》。《龙珠》中有许多不同的增幅耳环,KC对其中的每个耳环都有不同的评价值,因为耳环数量实在太多,KC想要将他们分成几组来使用。所有耳环都要使用,每组耳环一定要是连续的,并且每组耳环的评价值之和必须非负

SH大神和KC大神现在想要知道,耳环最多可以分成几组,由于这个问题实在是太easy了,他们不屑于写,于是这个问题就交给你来解决了。

例如4个耳环,评价值分别为2,3,-3,1。那么有4种方案(2 3 -3 1);(2 3 -3) (1);(2) (3 -3 1);(2) (3 -3) (1)。最多可以分为3组。

若无法满足分组条件,则输出Impossible

输入输出格式

输入格式: 第1行包含1个数N,代表耳环的数目。

第2至N+1行每行1个整数Ai。

输出格式: 输出文件有且仅有一行,包含1个正整数即为最多分组数。

若无法满足分组条件,则输出Impossible。

输入输出样例

输入样例#1: 4 2 3 -3 1 输出样例#1: 3

说明

【数据规模和约定】

30%的数据满足N≤20。

100%的数据满足N≤1000, Ai ≤100000。

解题思路

动态规划

边读入边处理前缀和add 从1到n扫一个数i,再从0-i-1扫一个数j,使得add[i]-add[j]>=0,且dp[j]+1>dp[i],此时更新dp[i]。 但是要注意,扫到的i必须满足条件:add[i]>=0,否则是无解的,因为前面的和已经为负了。当add[i]<0时直接跳到下一个i。 最后输出dp[n]。

这个思路类似对add数组求最长不下降子序列。

下面是code:

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int maxn=1005;
int n,s[maxn],f[maxn];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int t;
        cin>>t;
        s[i]=s[i-1]+t;
    };
    if(s[n]<0)
    {
        cout<<"Impossible";
        exit(0);
    }else
    {
        f[1]=0;f[0]=0;
        for(int i=1;i<=n;i++)
            if(s[i]>=0)
                for(int j=0;j<=i-1;j++)
                    if(s[i]-s[j]>=0&&f[j]+1>f[i])
                        f[i]=f[j]+1;
    };
    cout<<f[n];
    return 0;
};

下面是朋友写的一段代码,用的是最长不下降子序列做法,但是只有90分,因为没有判断add[i]>=0。(此处是理解难点,要多注意)

#include<iostream>
#include<algorithm>
using namespace std;
int f[1005],s[1005],n,a;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a;
        s[i]=s[i-1]+a;
        for(int j=1;j<=i;j++)
        {
            if(s[j]<=s[i])f[i]=max(f[i],f[j]);

        }
        f[i]++;

    }
    a=0;
    for(int i=1;i<=n;i++)
        {
            a=max(a,f[i]);
        }
        if(a==15){cout<<8;exit(0);}
        if(s[n]>0)cout<<a;
        else
        cout<<"Impossible";
}

感谢惠读

Tips

Cancel

Thanks a lot,I will be better!

scan possible
scan possible
Scan and give tips as you wish

OpenAlipayScan it and give tips as you wish

Wait a minute,Loading