UVALive7484 Association for the Country of Mububa(DP)

题目链接

题意很简单,给出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;
}
Zhao Li /
Published under (CC) BY-NC-SA in categories 算法  tagged with 动态规划