8
UVALive7484 Association for the Country of Mububa（DP）
source link: https://arminli.com/uvalive7484/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Armin's Blog
UVALive7484 Association for the Country of Mububa（DP）
March 25, 2016
题意很简单，给出 n 个数字，要分成最多的区间数，使每个区间内的和大于等于前一个区间和。
思路：sum[]表示前缀和，dp[i]表示前 i 个数字的最多区间数，presum[i]表示只考虑前 i 个数时，最后一个区间的和，这样只要从末端枚举直到和大于等于 presum[j]就 break。
#include<cstring>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
long long sum[3010];
long long presum[3010];
int dp[3010];
int main(){
int n;
sum[0] = 0;
while(~scanf("%d", &n)){
presum[0] = 0;
dp[0] = 0;
for(int i = 1; i <= n; i++){
scanf("%lld", &sum[i]);
sum[i] += sum[i-1];
}
for(int i = 1; i <= n; i++){
for(int j = i-1; j >= 0; j--){
long long temp = sum[i]-sum[j];
if(temp >= presum[j]){
presum[i] = temp;
dp[i] = dp[j]+1;
break;
}
}
}
cout << dp[n] << endl;
}
return 0;
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK