ccyy's coding zone
往前走,不要留恋路边的风景.
posts - 25,comments - 9,trackbacks - 0
Problem:http://acm.uestc.edu.cn/ShowProblem.aspx?ProblemID=1214&ContestID=126

Description:
给你一个长度为n的数列,有正有负,划分为不大于m断...使各段的和的最大值最小..

Method:
二分+DP判断可行性
刚开始的时候以为感觉这道题和poj1505很像....按1505的思路敲了..但是是不对的...因为有负数的情况...后来又用了一个贪心的方法来判断可行性...还是wa...发现贪心的方法是错的...后来用dp判断可行性才过了...

CODE:
C++语言: Uestc 1214
#include <stdio.h>
int n, m;
int arr[1010];
int dp[1010];
bool check(int x)
{
    int sum = 0;
    for(int i = 1; i <= n; i++)
        dp[i] = m + 1;
    dp[0] = 0;
    for(int i = 1; i <= n; i++)
    {
        sum = 0;
        for(int j = i; j > 0; j--)
        {
            sum += arr[j];
            if(sum <= x && dp[i] > dp[j - 1] + 1)
                dp[i] = dp[j - 1] + 1;
        }
    }
    return dp[n] <= m;
}
int main()
{
    int cs;
    scanf("%d", &cs);
    while(cs--)
    {
        scanf("%d %d", &n, &m);
        for(int i = 1; i <= n; i++)
            scanf("%d", &arr[i]);
        if(n == 1)
        {
            printf("%d\n", arr[1]);
            continue;
        }
        int low = -100000, high = 100000, ans = -1;
        int mark = 1;
        while(low <= high)
        {
            int mid = (low + high) / 2;
            if(check(mid))
            {
                ans = mid;
                high = mid - 1;
            }
            else low = mid + 1;
        }
        printf("%d\n", ans);
    }
}
阅读全文
类别:默认分类 查看评论
文章来源:http://hi.baidu.com/%D2%EC%B6%C8%BF%D5%BC%E4%5F%B5%DA%CB%C4%CE%AC/blog/item/08f3d69beb87da046f068c09.html
posted on 2010-05-04 22:00 ccyy 阅读(95) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理