UVA1629---Cake slicing

最新推荐文章于 2020-06-29 12:46:12 发布

Vanguard-xf

最新推荐文章于 2020-06-29 12:46:12 发布

阅读量788

点赞数

分类专栏： ACM 文章标签： acm 动态规划

本文链接：https://blog.csdn.net/xfzero/article/details/47425887

版权

ACM 专栏收录该内容

16 篇文章

订阅专栏

本文探讨了在解决动态规划问题时如何优化空间使用，通过减少不必要的内存分配和利用预处理来提高效率。实例展示了如何将状态空间表示为矩形，并通过枚举切分方式来最小化解决方案，同时避免了初始化时的超时问题。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

这题看懂了就不难,我做法算是dp中比较暴力
把每个状态看成(l,r,u,d)的矩形
然后把当前状态下所以可能(切的方式)状态枚举一遍取最小
然而我以前从没注意节约空间,这题d[][][][]空间开的太大,然后用memset初始化超时,debug半天

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<cstdlib>
#include<algorithm>
#include<stack>
#include<map>
#include<queue>
#include<vector>
using namespace std;
const int maxn = 23;


const int INF = 0x3f3f3f3f;
int dp[maxn][maxn][maxn][maxn],flag[maxn][maxn],sum[maxn][maxn],m,n,k;




//预处理让递归时求矩形有多少个标记时稍微快那么一点点
void getsum(){
    memset(sum,0,sizeof sum);
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            sum[i][j] = sum[i][j-1] +flag[i][j];
        }
    }
}
int findnum(int l,int r,int u,int d){
    int ans=0;
    for(int i=u;i<=d;i++){
        ans += sum[i][r] - sum[i][l-1];
        //也是一种小优化,我们需要知道的是是否为空,1,多
       // if(ans>=2) return ans;
    }
    return ans;
}


int dfs(int l,int r,int u,int d){
    int &ans = dp[l][r][u][d];
    if(ans>=0) return ans;
    int num = findnum(l,r,u,d);
    if(!num) return ans = INF;
    if(num==1) return ans = 0;
    ans = INF;
    for (int i=l;i<r;i++){
        ans = min(dfs(l,i,u,d)+dfs(i+1,r,u,d)+(d-u)+1,ans);
    }


    for (int i=u;i<d;i++){
        ans = min(dfs(l,r,u,i)+dfs(l,r,i+1,d)+(r-l)+1,ans);
    }
    return ans;
}
int main(){
	int kase=0;
	int a,b;
	while(cin>>m>>n>>k){
        memset(dp,-1,sizeof dp);
        memset(flag,0,sizeof flag);
        for(int i=1;i<=k;i++){
            cin>>a>>b;flag[a][b]=1;
        }
        getsum();
        printf("Case %d: %d\n",++kase,dfs(1,n,1,m));
    }
    return 0;
}