# The Fourth Dimension Space

## UESTC D Divide DP

dp[0] = 0

dp[ i ] = min{ dp[ j ] + 1 }, j < i 且 sum(j + 1, i) <= ans.

#include<iostream>
#include
<algorithm>
using namespace std;
#define INF 999999999
int n,m;
int a[1010];
int dp[1010];
int sum[1010];

bool check(int mid)
{

int i,j;
memset(dp,
0,sizeof(dp));

for(i=1;i<=n;i++)

{
dp[i]
=INF;

for(j=0;j<i;j++)

{

if(sum[i]-sum[j]<=mid)
dp[i]
=min(dp[i],dp[j]+1);
}

}

if(dp[n]<=m)

return true;

else

return false;
}

int main()
{

int t;

int i,j;
scanf(
"%d",&t);

while(t--)

{
scanf(
"%d%d",&n,&m);

for(i=1;i<=n;i++)

{
scanf(
"%d",&a[i]);
sum[i]
=sum[i-1]+a[i];
}

int l=-100000;

int r=100000;

int ans=-1;

while(l<=r)

{

int mid=(l+r)>>1;

if(check(mid))

{
r
=mid-1;
ans
=mid;
}

else

{

l
=mid+1;
}

}

printf(
"%d\n",ans);

}

return 0;

}

posted on 2010-05-02 19:55 abilitytao 阅读(1117) 评论(1)  编辑 收藏 引用

### 评论

#### #re: UESTC D Divide DP[未登录] 2010-05-05 09:08 yoyo

Hi, man.
The problems and solution or algorithms posted here are terrific, but in most time readers here are hard to see the description of problems.

Would you provide the problem description or kind of info, before giving your ideas and algorithm code? Or a URL to introduce problems hosted by "UESTC"?