Game
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 691 Accepted Submission(s): 277
Problem Description
onmylove has invented a game on n × m grids. There is one positive integer on each grid. Now you can take the numbers from the grids to make your final score as high as possible. The way to get score is like
the following:
● At the beginning, the score is 0;
● If you take a number which equals to x, the score increase x;
● If there appears two neighboring empty grids after you taken the number, then the score should be decreased by 2(x&y). Here x and y are the values used to existed on these two grids. Please pay attention that "neighboring grids" means there exits and only exits one common border between these two grids.
Since onmylove thinks this problem is too easy, he adds one more rule:
● Before you start the game, you are given some positions and the numbers on these positions must be taken away.
Can you help onmylove to calculate: what's the highest score onmylove can get in the game?
the following:
● At the beginning, the score is 0;
● If you take a number which equals to x, the score increase x;
● If there appears two neighboring empty grids after you taken the number, then the score should be decreased by 2(x&y). Here x and y are the values used to existed on these two grids. Please pay attention that "neighboring grids" means there exits and only exits one common border between these two grids.
Since onmylove thinks this problem is too easy, he adds one more rule:
● Before you start the game, you are given some positions and the numbers on these positions must be taken away.
Can you help onmylove to calculate: what's the highest score onmylove can get in the game?
Input
Multiple input cases. For each case, there are three integers n, m, k in a line.
n and m describing the size of the grids is n ×m. k means there are k positions of which you must take their numbers. Then following n lines, each contains m numbers, representing the numbers on the n×m grids.Then k lines follow. Each line contains two integers, representing the row and column of one position
and you must take the number on this position. Also, the rows and columns are counted start from 1.
Limits: 1 ≤ n, m ≤ 50, 0 ≤ k ≤ n × m, the integer in every gird is not more than 1000.
n and m describing the size of the grids is n ×m. k means there are k positions of which you must take their numbers. Then following n lines, each contains m numbers, representing the numbers on the n×m grids.Then k lines follow. Each line contains two integers, representing the row and column of one position
and you must take the number on this position. Also, the rows and columns are counted start from 1.
Limits: 1 ≤ n, m ≤ 50, 0 ≤ k ≤ n × m, the integer in every gird is not more than 1000.
Output
For each test case, output the highest score on one line.
Sample Input
2 2 1 2 2 2 2 1 1 2 2 1 2 7 4 1 1 1
Sample Output
4 9
Hint
As to the second case in Sample Input, onmylove gan get the highest score when calulating like this: 2 + 7 + 4 - 2 × (2&4) - 2 × (2&7) = 13 - 2 × 0 - 2 × 2 = 9.
Author
onmylove
Source
Recommend
lcy
- 题意: 给定一个 n * m 大小的矩阵, 矩阵中每个格子都有一个不大于 1000 的正整数,
- * 现在要从矩阵中选出若干个格子, 使得得分最大. 得分等于选取的格子里的数字
- * 和. 如果有两个格子相邻, 则得分将减去 2 * (x & y), x 和 y 为相邻两个格
- * 子内的数字. 此外, 还有一些格子是必选的.
- * 解法: 此题是个最大流算法, 和 NOI 国家集训队论文上的最大流题目类似. 建图方法
- * 是设置一个超级源点和一个超级汇点, 将横坐标和纵坐标之和为偶数的格子和源
- * 点相连, 边权值为格子的数值. 将横坐标和纵坐标之和为奇数的格子和汇点相连,
- * 边权值为格子的数值, 如果两个格子相邻, 则在它们所代表的顶点之间连一条边,
- * 权值为 2 * (x & y) . 对于必选的顶点, 将它们和源点或者汇点相连的边权值
- * 改为正无穷, 最大得分数为所有格子数值相加减去图的最大流
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int VM=101000; //所谓的TLE都是被这个数据开小了导致的,,,God const int EM=500100; const int INF=0x3f3f3f3f; struct Edge{ int to,nxt; int cap; }edge[EM<<1]; int n,m,k,cnt,head[VM],map[110][110]; int dep[VM],gap[VM],cur[VM],aug[VM],pre[VM]; void addedge(int cu,int cv,int cw){ edge[cnt].to=cv; edge[cnt].cap=cw; edge[cnt].nxt=head[cu]; head[cu]=cnt++; edge[cnt].to=cu; edge[cnt].cap=0; edge[cnt].nxt=head[cv]; head[cv]=cnt++; } int src,des; int SAP(int n){ int max_flow=0,u=src,v; int id,mindep; aug[src]=INF; pre[src]=-1; memset(dep,0,sizeof(dep)); memset(gap,0,sizeof(gap)); gap[0]=n; for(int i=0;i<=n;i++) cur[i]=head[i]; // 初始化当前弧为第一条弧 while(dep[src]<n){ int flag=0; if(u==des){ max_flow+=aug[des]; for(v=pre[des];v!=-1;v=pre[v]){ // 路径回溯更新残留网络 id=cur[v]; edge[id].cap-=aug[des]; edge[id^1].cap+=aug[des]; aug[v]-=aug[des]; // 修改可增广量,以后会用到 if(edge[id].cap==0) // 不回退到源点,仅回退到容量为0的弧的弧尾 u=v; } } for(int i=cur[u];i!=-1;i=edge[i].nxt){ v=edge[i].to; // 从当前弧开始查找允许弧 if(edge[i].cap>0 && dep[u]==dep[v]+1){ // 找到允许弧 flag=1; pre[v]=u; cur[u]=i; aug[v]=min(aug[u],edge[i].cap); u=v; break; } } if(!flag){ if(--gap[dep[u]]==0) /* gap优化,层次树出现断层则结束算法 */ break; mindep=n; cur[u]=head[u]; for(int i=head[u];i!=-1;i=edge[i].nxt){ v=edge[i].to; if(edge[i].cap>0 && dep[v]<mindep){ mindep=dep[v]; cur[u]=i; // 修改标号的同时修改当前弧 } } dep[u]=mindep+1; gap[dep[u]]++; if(u!=src) // 回溯继续寻找允许弧 u=pre[u]; } } return max_flow; } int main(){ //freopen("input.txt","r",stdin); while(~scanf("%d%d%d",&n,&m,&k)){ cnt=0; memset(head,-1,sizeof(head)); src=0; des=n*m+1; int sum=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ scanf("%d",&map[i][j]); sum+=map[i][j]; } int x,y; while(k--){ scanf("%d%d",&x,&y); if((x+y)%2==0) addedge(src,(x-1)*m+y,INF); else addedge((x-1)*m+y,des,INF); } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ int tmp=(i-1)*m+j; if((i+j)%2==0) addedge(src,tmp,map[i][j]); else addedge(tmp,des,map[i][j]); } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if((i+j)%2==0){ int tmp=(i-1)*m+j; if(i>1) addedge(tmp,tmp-m,2*(map[i][j]&map[i-1][j])); if(i<n) addedge(tmp,tmp+m,2*(map[i][j]&map[i+1][j])); if(j>1) addedge(tmp,tmp-1,2*(map[i][j]&map[i][j-1])); if(j<m) addedge(tmp,tmp+1,2*(map[i][j]&map[i][j+1])); } printf("%d\n",sum-SAP(des+1)); } return 0; }
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
HDU最全ac代码
hdu动态规划算法集锦
自己做的HDU ACM已经AC的题目
hdu题目分类
HDU图论题目分类
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
Hdu 1237 解题代码