注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ3997][TJOI2015]组合数学  

2015-04-23 21:45:19|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3997: [TJOI2015]组合数学

Time Limit: 20 Sec  Memory Limit: 128 MB
Submit: 168  Solved: 116
[Submit][Status][Discuss]

Description

 给出一个网格图,其中某些格子有财宝,每次从左上角出发,只能向下或右走。问至少走多少次才能将财宝捡完。此对此问题变形,假设每个格子中有好多财宝,而每一次经过一个格子至多只能捡走一块财宝,至少走多少次才能把财宝全部捡完。

Input

 第一行为正整数T,代表数据组数。

每组数据第一行为正整数N,M代表网格图有N行M列,接下来N行每行M个非负整数,表示此格子中财宝数量,0代表没有

Output

 输出一个整数,表示至少要走多少次。

Sample Input

1 3 3 0 1 5 5 0 0 1 0 0

Sample Output

10

HINT

 N<=1000,M<=1000.每个格子中财宝数不超过10^6

Solution

考虑一种不太靠谱的建图,拆点分为出入,出向入连0,入向出连点权,答案为“最大割”,对偶一下等价于找一条从右上到左下的路径权值最大,dp解决

Code

/**************************************************************
    Problem: 3997
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:832 ms
    Memory:8808 kb
****************************************************************/
 
#include<cstdio>
#define N 1010
int _,n,m,i,j,a[N][N],f[N][N],aa,ans;
char B[1<<15],*S=B,*T=B,ch;
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
int F(){
    while(ch=getc(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
#define max(a,b)(a>b?a:b)
int main(){
    for(_=F();_--;printf("%d\n",ans)){
        n=F(),m=F();ans=0;
        for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)a[i][j]=F(),f[i][j]=0;
        for(i=1;i<=n;ans=max(ans,f[i][1]),i++)
        for(j=m;j;j--)f[i][j]=max(f[i-1][j+1]+a[i][j],max(f[i-1][j],f[i][j+1]));
    }
}
  评论这张
 
阅读(192)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018