UVA 1629 记忆化搜索

2019-11-06 08:42:33

字体：大中小

来源：转载

供稿：网友

题意

有一个n行m列的蛋糕，切蛋糕，要求最后每一块蛋糕上恰好有一个樱桃。问切割线总长度最小是多少？

题解

记忆化搜索。设dp[l][r][u][d]为切割从横向从l到r，纵向从u到d的一块蛋糕，切割线总长度的最小值。然后不断DFS搜索并记录dp值，最后dp[0][m][n][0]即为所求。

代码

#include <iostream>#include<cstdio>#include<algorithm>#include<cstring>#define INF 1e9using namespace std;int mp[30][30];int dp[30][30][30][30];int countCheery(int l,int r,int u,int d){ int num=0; for(int i=d+1;i<=u;i++){ for(int j=l+1;j<=r;j++){ if(mp[i][j]==1) num++; if(num>=2) return 2; } } return num;}int dfs(int l,int r,int u,int d){ int& ans=dp[l][r][u][d]; if(ans!=-1) return ans; int num=countCheery(l,r,u,d); if(num==1) return ans=0; if(num==0) return ans=INF; ans=INF; for(int i=l+1;i<r;i++){ ans=min(ans,dfs(l,i,u,d)+dfs(i,r,u,d)+u-d); } for(int i=d+1;i<u;i++){ ans=min(ans,dfs(l,r,i,d)+dfs(l,r,u,i)+r-l); } return ans;}int main(){ int n,m,k; int ks=1; while(scanf("%d%d%d",&n,&m,&k)!=EOF){ memset(dp,-1,sizeof(dp)); memset(mp,0,sizeof(mp)); for(int i=0;i<k;i++){ int a,b; scanf("%d%d",&a,&b); mp[a][b]=1; } PRintf("Case %d: %d/n",ks++,dfs(0,m,n,0)); } return 0;}

上一篇：[BZOJ]1009 GT考试

下一篇：【机器人学】机器人开源项目KDL源码学习：（4）examples中的CMakeList.txt文件解读