首页 > 其他 > 详细

2018.7.19模拟考试

时间:2018-07-19 19:55:04      阅读:160      评论:0      收藏:0      [点我收藏+]

我的运气真的有够差...代码没能提交到评测姬上去...虽然就算提交了也是爆零

T1 题意简述:合并数列相邻项(也可不合并)使得数列单调不减并使项数最多。求原项数与合并后项

             数的差。

             0<n<=5000,0<a[i]<=2147483647

   解题思路:首先考虑贪心,显然错误(如:5 1 7 7 8)。

             考虑dp。dp[i]表示数列前i个数合并后最多的项数,lst[i]表示以第i项结尾的需合并区

             间的和。

             考虑递推方程,发现分两种情况。(枚举k)

             1.a[k]>=lst[i] dp[k]=dp[i]+1,lst[k]=a[k],k++;

             2.a[k]<lst[i] lst[i]+=a[k],k++。直至满足情况一。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
ll n,dp[5001],sum[5001],a[5001],lst[5001];
int main()
{
    freopen("tower.in","r",stdin);
    freopen("tower.out","w",stdout);
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++)
        scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
    dp[1]=1;lst[1]=a[1];
    for(ll i=2;i<=n;i++)
        for(ll j=i-1;j>=0;j--)
            if(sum[i]-sum[j]>=lst[j])
            {
                dp[i]=dp[j]+1;
                lst[i]=sum[i]-sum[j];
                break;
            }
    printf("%lld\n",n-dp[n]);
    return 0;
}

 

2018.7.19模拟考试

原文:https://www.cnblogs.com/water-radish/p/9337902.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!