Problem:http://acm.uestc.edu.cn/ShowProblem.aspx?ProblemID=1214&ContestID=126
Description:
给你一个长度为n的数列,有正有负,划分为不大于m断...使各段的和的最大值最小..
Method:
二分+DP判断可行性
刚开始的时候以为感觉这道题和poj1505很像....按1505的思路敲了..但是是不对的...因为有负数的情况...后来又用了一个贪心的方法来判断可行性...还是wa...发现贪心的方法是错的...后来用dp判断可行性才过了...
CODE:
#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 阅读(96)
评论(0) 编辑 收藏 引用