Problem：http://acm.uestc.edu.cn/ShowProblem.aspx?ProblemID=1214&ContestID=126
Description:
給你一個長度為n的數列，有正有負，劃分為不大于m斷...使各段的和的最大值最小..
Method:
二分+DP判斷可行性
剛開始的時候以為感覺這道題和poj1505很像....按1505的思路敲了..但是是不對的...因為有負數的情況...后來又用了一個貪心的方法來判斷可行性...還是wa...發(fā)現貪心的方法是錯的...后來用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 閱讀(108)
評論(0) 編輯 收藏 引用