uva 1629——Cake slicing

╰+攻爆jí腚メ 2022-08-18 11:31 20阅读 0赞

题意：有一个n行m列网格蛋糕上有一些樱桃，每次可以把蛋糕一刀切成两块，最后使每块蛋糕上都有一个樱桃且切割线总长度最小。

思路：区间dp，记忆化搜索整个过程，然后分区间从上到下，从左到右，分区间递归找到找到满足条件的最小值。

code：

#include <bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    
    const int INF=0x3fffffff;
    const int inf=-INF;
    const int N=22;
    const int M=2005;
    const int mod=1000000007;
    const double pi=acos(-1.0);
    
    #define cls(x,c) memset(x,c,sizeof(x))
    #define cpy(x,a) memcpy(x,a,sizeof(a))
    #define ft(i,s,n) for (int i=s;i<=n;i++)
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    #define lrt  rt<<1
    #define rrt  rt<<1|1
    #define middle int m=(r+l)>>1
    #define lowbit(x) (x&-x)
    #define pii pair<int,int>
    #define mk make_pair
    #define IN freopen("in.txt","r",stdin);
    #define OUT freopen("out.txt","w",stdout);
    
    int dp[N][N][N][N],g[N][N];
    int ok(int u,int d,int l,int r)
    {
        int ans=0;
        ft(i,u+1,d) ft(j,l+1,r) if (g[i][j]) ans++;
        return ans;
    }
    int sol(int u,int d,int l,int r)
    {
        int& ans=dp[u][d][l][r];
        if (ans!=-1) return ans;
        if (ok(u,d,l,r)==1) return ans=0;
        if (ok(u,d,l,r)==0) return ans=INF;
        int res=INF;
        ft(i,u+1,d-1) res=min(res,sol(u,i,l,r)+sol(i,d,l,r)+r-l);
        ft(i,l+1,r-1) res=min(res,sol(u,d,l,i)+sol(u,d,i,r)+d-u);
        return ans=res;
    }
    int main()
    {
        int ca=1;int m,n,k,a,b;
        while (~scanf("%d %d %d",&m,&n,&k))
        {
            cls(dp,-1);cls(g,0);
            ft (i,1,k) scanf("%d %d",&a,&b),g[a][b]=1;
            printf("Case %d: %d\n",ca++,sol(0,m,0,n));
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，20人围观）

还没有评论，来说两句吧...

相关阅读

相关【MEX】CF1629 C

[Problem - C - Codeforces][] 题意： ![3b96010d5d4e4308a6e03f37a292c9af.png][] ![c7302633

た入场券/ 2024年03月17日 19:35/ 0 赞/ 169 阅读

相关 matlab定义sliced类型,Sliced Variables

Characteristics of a Sliced Variable If a variable in a parfor-loop has all the followi

秒速五厘米/ 2023年01月17日 08:21/ 0 赞/ 290 阅读

相关 51Nod 1629 B君的圆锥

[1629 B君的圆锥][1629_B] ![ok.png][] 基准时间限制：1 秒空间限制：131072 KB 分值: 10 [难度：2级算法题][2] ![sta

偏执的太偏执、/ 2022年09月27日 00:25/ 0 赞/ 249 阅读

相关 Cake PHP framework

主页是: [http://sputnik.pl/cake/][http_sputnik.pl_cake] 好象是个不错的php框架,没时间去读他,先记下了; \[cop

我会带着你远行/ 2022年08月27日 14:47/ 0 赞/ 115 阅读

相关 HDOJ 5640-King's Cake【数学】

King's Cake Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/

た入场券/ 2022年08月21日 03:14/ 0 赞/ 144 阅读

相关 uva 1629——Cake slicing

题意：有一个n行m列网格蛋糕上有一些樱桃，每次可以把蛋糕一刀切成两块，最后使每块蛋糕上都有一个樱桃且切割线总长度最小。思路：区间dp，记忆化搜索整个过程，然后分区

╰+攻爆jí腚メ/ 2022年08月18日 11:31/ 0 赞/ 21 阅读

相关 slice

概念 Slice切片是对底层数组Array的封装，在内存中的存储本质就是数组，体现为连续的内存块，Go语言中的数组定义之后，长度就已经固定了，在使用过程中并不能改变其长度，而

Love The Way You Lie/ 2022年06月17日 09:42/ 0 赞/ 263 阅读

相关 B - Cake

B - Cake HPU专题训练（-1）GCD&&素筛&&快速幂\_\_\_\_\_B - Cake 一次生日Party可能有p人或者q人参加,现准备有一个大蛋糕

Love The Way You Lie/ 2022年06月01日 07:50/ 0 赞/ 220 阅读

相关数学题(直线分割)UVA 10167-Birthday Cake

数学题(直线分割)UVA 10167-Birthday Cake -------------------- 题目链接：[10167 - Birthday

超、凢脫俗/ 2022年05月15日 22:54/ 0 赞/ 257 阅读

相关 [BZOJ 3498] [PA 2009] Cakes

Description \\(n\\) 个点 \\(m\\) 条边，每个点有一个点权 \\(a\_i\\)。对于任意一个三元环 \\((i,j,k)(i<j<k)\

墨蓝/ 2021年12月22日 04:09/ 0 赞/ 343 阅读