首页 > 代码库 > [hdu 2686]Matrix

[hdu 2686]Matrix

2024-07-23 16:32:41   218人阅读

网上说这道题的题解是费用流

我粗粗看了一下数据范围，觉得出题者似乎是让我们用 “大（d）屁（p）” 的样子，为了尊重出题人，我还是谢谢吧喵~

 

首先，一条回路可以看做是两条路齐头并进，这是 大屁 和 费永柳 的共同思想

故我们可用一条条次对角线（即 x+y=k  的对角线）来划分状态

考虑枚举对角线上两个点 x1，y1，x2，y2
很大力地用 f[x1][y1][x2][y2] 表示两条路分别走到 点（x1, y1）和 点（x2, y2）时的最佳方案

这样 f[x1][y1][x2][y2] 就可以由 f[x1-1][y1][x2-1][y2], f[x1-1][y1][x2][y2-1], f[x1][y1-1][x2-1][y2], f[x1][y1-1][x2][y2-1] 来得到（丧心病狂）

还有当 点（x1, y1）和 点（x2, y2）在对角线上相邻时情况特殊，因为 点（x1-1, y1）和 点（x2, y2-1）重合了，需要特别考虑（真是丧心病狂）

 

虽然看上去很恶心，但我觉得再怎么说短也是一大优势，你的费用流有这么短喵？

 

#include <cstdio>#include <cstring>#define max(x, y) ((x)>(y) ? (x):(y))const int size=32;int n;int a[size][size];int f[size][size][size][size];inline int getint();inline void putint(int);int main(){	while (scanf("%d", &n)!=EOF)	{		for (int i=1;i<=n;i++)			for (int j=1;j<=n;j++)				a[i][j]=getint();		memset(f, 0, sizeof f);		f[2][1][1][2]=a[1][1]+a[1][2]+a[2][1];		for (int i=4;i<2*n;i++)			for (int y1=i<=n+1?1:i-n;y1<i-1 && y1<n;y1++)				for (int y2=y1+1;y2<i && y2<=n;y2++)				{					int x1=i-y1, x2=i-y2;					if (y2-y1==1) f[x1][y1][x2][y2]=max(max(f[x1][y1-1][x2][y1], f[x2][y1][x2-1][y2]), f[x1][y1-1][x2-1][y2]);					else f[x1][y1][x2][y2]=max(max(f[x1-1][y1][x2-1][y2], f[x1-1][y1][x2][y2-1]), max(f[x1][y1-1][x2-1][y2], f[x1][y1-1][x2][y2-1]));					f[x1][y1][x2][y2]+=a[x1][y1]+a[x2][y2];				}		putint(a[n][n]+f[n][n-1][n-1][n]);	}	return 0;}inline int getint(){	register int num=0;	register char ch;	do ch=getchar(); while (ch<‘0‘ || ch>‘9‘);	do num=num*10+ch-‘0‘, ch=getchar(); while (ch>=‘0‘ && ch<=‘9‘);	return num;}inline void putint(int num){	char stack[15];	register int top=0;	for ( ;num;num/=10) stack[++top]=num%10+‘0‘;	for ( ;top;top--) putchar(stack[top]);	putchar(‘\n‘);}

 

[hdu 2686]Matrix


联系
我们