我的运气真的有够差...代码没能提交到评测姬上去...虽然就算提交了也是爆零
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; }
原文：https://www.cnblogs.com/water-radish/p/9337902.html