本文共 1819 字，大约阅读时间需要 6 分钟。
有一个n行m列的网格蛋糕，上面有一些樱桃。求使得每块蛋糕上都有一个樱桃的分割最小长度
思路：dp。
#include #include #include #include #include #include #include #include #include #include #include #include #include #define eps 1e-6 #define LL long long using namespace std; const int maxn = 100 + 5;const int INF = 10000000;int d[22][22][22][22];int n, m, K, kase = 0;//樱桃数量 int cherry[22][22], sumv[22][22];int cpu(int a, int b, int c, int d) { return sumv[b][d] - sumv[a-1][d] - sumv[b][c-1] + sumv[a-1][c-1];}int dp(int begx, int endx, int begy, int endy, int cherrynum) { int& ans = d[begx][endx][begy][endy]; if(cherrynum == 1) return 0; if(ans != -1) return ans; ans = INF; for(int i = begx; i < endx; i++) if(cpu(begx, i, begy, endy) > 0 && cpu(begx, i, begy, endy) < cherrynum) ans = min(ans, dp(begx, i, begy, endy, cpu(begx, i, begy, endy))+dp(i+1, endx, begy, endy, cherrynum-cpu(begx, i, begy, endy))+endy-begy+1); for(int i = begy; i < endy; i++) if(cpu(begx, endx, begy, i) > 0 && cpu(begx, endx, begy, i) < cherrynum) ans = min(ans, dp(begx, endx, begy, i, cpu(begx, endx, begy, i))+dp(begx, endx, i+1, endy, cherrynum-cpu(begx, endx, begy, i))+endx-begx+1); return ans; }void init() { memset(d, -1, sizeof(d)); memset(cherry, 0, sizeof(cherry)); memset(sumv, 0, sizeof(sumv)); int x, y; for(int i = 0; i < K; i++) { cin >> x >> y; cherry[x][y] = 1; } for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) sumv[i][j] = sumv[i][j-1] + sumv[i-1][j] + cherry[i][j] - sumv[i-1][j-1];}void solve() { printf("Case %d: %d\n", ++kase, dp(1, n, 1, m, K));}int main() { //freopen("input.txt", "r", stdin); while(scanf("%d%d%d", &n, &m, &K) == 3) { init(); solve(); } return 0;}
转载于:https://www.cnblogs.com/hrhguanli/p/5105756.html