The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

UESTC D Divide DP

这个动态规划还要好好研究下,二分+dp,想法很不错,而且这里有个trick,就是这个最大值可以是负数,一开始没有注意到还我傻呆呆的Wa了N次。。。好了,不能再做题了,赶紧看系统结构吧。不然要杯具了。。。

官方解题报告:
首先二分答案ans,然后问题变为是否能够将N个数分为不超过M堆,并且每堆的和都不超过ans。因为存在负数,所以贪心的做法是错误的。这可以用动态规划求解,用dp[ i ]表示考虑前i个数,至少需要分dp[ i ]堆才能使每堆和不超过ans.

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 阅读(1140) 评论(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"?

Thanks in advance!

yoyo   回复  更多评论   


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