https://vjudge.net/problem/UVA-1214
有一块棋盘，上面有两个格子写着2，两个格子写着3，剩下的格子要么写着0，要么写着1。
你可以在0上面连线，还可以从2和3引出线，要求分别连接两个2和两个3，并且这些线不能交叉，也不能经过1。每个格子里面只能有1条线。线只能水平或垂直放置（可以拐弯，但是每一段都只能水平或垂直），线的长度为这条线跨过的格子的边界。
如图结果为18
输出最小的两条线长度的和。
利用轮廓线dp
相当于摆放11种拼图
因为折线和长线入度等于出度，而短线只会从2和3引出来，那么无论怎么摆放，要求不能突然结束，也不能把标为2的线和标为3的线连接起来，那么有效的摆放方法一定是连接两个2和连接两个3的，取最小值就可以了
还有就是如果用递推会非常慢，因为枚举了很多根本不会转移到的状态，所以用了记忆化搜索……
还有就是可以新开一个数组，用3进制压位，可以减少memset的时间
uvalive挂了，最近5小时的提交全是wrong answer
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cctype>
#include<cassert>
#define REP(i,a,b) for(register int i=(a); i<(b); i++)
#define REPE(i,a,b) for(register int i=(a); i<=(b); i++)
#define PERE(i,a,b) for(register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
int n,m;
int msk1, msk2;
char a[10][10];
int dp[10][10][1<<20];//4**10
#define UP(x) (k&3)
#define LEFT(x) ((k>>(m*2))&3)
char blk[10][5]={//LEFT UP RIGHT DOWN
"0100", "0010", "0001", "1000",
"0110", "0011", "1001", "1100",
"1010", "0101"
};
inline int place(int k, int x, int y) {
if(x==m) {y++;x=0;}
if(y==n) return 0;
int ans=dp[x][y][k];
if(ans>=0) return ans;
else ans=0x3f3f3f3f;
int N=a[y][x]-‘0‘, t;
if(N==1) {
if(UP(k)==0 && LEFT(k)==0) {
t=k>>2;
ans=min(ans, place(t, x+1, y));
}
} else if(N>0) {
REP(i,0,4) {
int l=(blk[i][0]-‘0‘)*N, u=(blk[i][1]-‘0‘)*N;
int d=(blk[i][3]-‘0‘)*N, r=(blk[i][2]-‘0‘)*N;
if(x==m-1 && r) continue;
if(y==n-1 && d) continue;
if(UP(k)!=u) continue;
if(LEFT(k)!=l) continue;
t=(k&msk1)>>2; t|=r<<(m*2); t|=d<<(m*2-2);
ans=min(ans, place(t, x+1, y)+1);
}
} else {
REP(i,4,10) REPE(j,2,3) {
int l=(blk[i][0]-‘0‘)*j, u=(blk[i][1]-‘0‘)*j;
int d=(blk[i][3]-‘0‘)*j, r=(blk[i][2]-‘0‘)*j;
if(x==m-1 && r) continue;
if(y==n-1 && d) continue;
if(UP(k)!=u) continue;
if(LEFT(k)!=l) continue;
t=(k&msk1)>>2; t|=r<<(m*2); t|=d<<(m*2-2);
ans=min(ans, place(t, x+1, y)+2);
}
if(UP(k)==0 && (!x || LEFT(k)==0)) {
t=k>>2;
ans=min(ans, place(t, x+1, y));
}
}
dp[x][y][k]=ans;
return ans;
}
int main() {
while(~scanf("%d%d", &n, &m) && n && m) {
REP(i,0,n) REP(j,0,m) do a[i][j]=getchar(); while(a[i][j]<‘0‘);
msk1=(1<<(m*2))-1;
memset(dp,-1,sizeof dp);
int ans=place(0,0,0);
if(ans<0x3f3f3f3f)
printf("%d\n", ans/2);
else
puts("0");
}
}
原文：https://www.cnblogs.com/sahdsg/p/12297012.html