2020-2021:teams:wangzai_milk:weekly:poj_2411
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:weekly:poj_2411 [2020/05/09 12:06] zars19 创建 |
2020-2021:teams:wangzai_milk:weekly:poj_2411 [2020/05/10 01:33] (当前版本) zars19 ↷ 页面2020-2021:teams:wangzai_milk:poj_2411被移动至2020-2021:teams:wangzai_milk:weekly:poj_2411 |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| [[http://poj.org/problem?id=2411|POJ 2411]] | [[http://poj.org/problem?id=2411|POJ 2411]] | ||
| - | |||
| - | 有横向运输和纵向运输的两种矿（要送到左端/上方），每个格子只能建一种方向（横/纵）的管道，最大化送到的矿的价值。 | ||
| - | |||
| - | **题解**：想象一下对于每一格子来说如果它建横向那它左边必然都是横向才有意义，纵向同理。搞一下前缀和，状态转移<code cpp>dp[i][j]=max(dp[i-1][j]+prea[i][j]-prea[i-1][j],dp[i][j-1]+preb[i][j]-preb[i][j-1])</code> | ||
| <code cpp> | <code cpp> | ||
| 行 12: | 行 8: | ||
| #include<cstdlib> | #include<cstdlib> | ||
| using namespace std; | using namespace std; | ||
| - | int n,m,dp[505][505],prea[505][505],preb[505][505]; | + | int h,w; |
| + | long long f[12][(1<<12)]; | ||
| + | int read() | ||
| + | { | ||
| + | int x=0,f=1;char c=getchar(); | ||
| + | while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} | ||
| + | while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} | ||
| + | return x*f; | ||
| + | } | ||
| int main() | int main() | ||
| { | { | ||
| - | while(~scanf("%d%d",&n,&m)) | + | h=read(),w=read(); |
| + | while(h&&w) | ||
| { | { | ||
| - | if(!n&&!m)return 0; | + | if((h*w)%2){puts("0"),h=read(),w=read();continue;} |
| - | for(int i=1;i<=n;i++) | + | memset(f,0,sizeof(f)); |
| - | for(int j=1;j<=m;j++) | + | if(!h&&!w)break; |
| - | { | + | for(int i=1;i<=h;i++) |
| - | scanf("%d",&prea[i][j]); | + | |
| - | prea[i][j]+=prea[i][j-1]+prea[i-1][j]-prea[i-1][j-1]; | + | |
| - | } | + | |
| - | for(int i=1;i<=n;i++) | + | |
| - | for(int j=1;j<=m;j++) | + | |
| - | { | + | |
| - | scanf("%d",&preb[i][j]); | + | |
| - | preb[i][j]+=preb[i][j-1]+preb[i-1][j]-preb[i-1][j-1]; | + | |
| - | } | + | |
| - | for(int i=1;i<=n;i++) | + | |
| - | for(int j=1;j<=m;j++) | + | |
| { | { | ||
| - | dp[i][j]=max(dp[i-1][j]+prea[i][j]-prea[i-1][j],dp[i][j-1]+preb[i][j]-preb[i][j-1]); | + | for(int j=0;j<(1<<w);j++) |
| + | { | ||
| + | if(i==1) | ||
| + | { | ||
| + | f[i][j]=1; | ||
| + | for(int l=1;l<(1<<w);l<<=1) | ||
| + | { | ||
| + | if((j&l)==0) | ||
| + | { | ||
| + | if((l<<1)>=(1<<w)){f[i][j]=0;break;} | ||
| + | else if(j&(l<<1)){f[i][j]=0;break;} | ||
| + | else l<<=1; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | for(int k=0;k<(1<<w);k++) | ||
| + | { | ||
| + | if(!f[i-1][k])continue; | ||
| + | f[i][j]+=f[i-1][k]; | ||
| + | for(int l=1;l<(1<<w);l<<=1) | ||
| + | { | ||
| + | if(k&l) | ||
| + | { | ||
| + | if(j&l){f[i][j]-=f[i-1][k];break;} | ||
| + | } | ||
| + | else if((j&l)==0) | ||
| + | { | ||
| + | if((l<<1)>=(1<<w)){f[i][j]-=f[i-1][k];break;} | ||
| + | else if(j&(l<<1)){f[i][j]-=f[i-1][k];break;} | ||
| + | else if(k&(l<<1)){f[i][j]-=f[i-1][k];break;} | ||
| + | else l<<=1; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | } | ||
| } | } | ||
| - | printf("%d\n",dp[n][m]); | + | printf("%lld\n",f[h][0]); |
| + | h=read(),w=read(); | ||
| } | } | ||
| return 0; | return 0; | ||
| } | } | ||
| </code> | </code> | ||
2020-2021/teams/wangzai_milk/weekly/poj_2411.1588997161.txt.gz · 最后更改: 2020/05/09 12:06 由 zars19
