首页 > 其他分享 >Problem: E. Chocolate Bar

Problem: E. Chocolate Bar

时间:2023-11-29 17:33:53浏览次数:30  
标签:Bar int long Chocolate return Problem define dp mod

image
题意:
给定一个n m个方块组成的巧克力块,最终要吃到k个方块
有两种切的方式:
(n m)
1.横着切,成本是m m
2.竖着切,成本是n n

做法:
考虑记忆化搜索,使用dp[n][m][k]代表一个n*m的巧克力最后要得到k块所需要的最小成本
状态转移:把每一次切的动作看作是一次转移:
以n,m,k为例
1.横着切,那么每次的成本是mxm,此时k的获得可以这样表示,我们枚举一层j从0-k,j表示前面那部分获得的巧克力,从而k-j表示后面的部分获得的巧克力
2.竖着切,成本就是nxn,k的表示和横着切一样

点击查看代码
// Problem: E. Chocolate Bar
// Contest: Codeforces - Educational Codeforces Round 1
// URL: https://codeforces.com/contest/598/problem/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Author: a2954898606
// Create Time:2023-11-29 14:53:30
// 
// Powered by CP Editor (https://cpeditor.org)

/*
    /\_/\
   (o   o)
  /      \
 // ^ ^  \\
///      \\\
 \       |
  \_____/
 /\_  _/\
 */
#include<bits/stdc++.h>

#define all(X) (X).begin(),(X).end()
#define all2(X) (X).begin()+1,(X).end()
#define pb push_back
#define mp make_pair
#define sz(X) (int)(X).size()

#define YES cout<<"YES"<<endl
#define Yes cout<<"Yes"<<endl
#define NO cout<<"NO"<<endl
#define No cout<<"No"<<endl

using namespace std;
typedef long long unt;
typedef vector<long long> vt_unt;
typedef vector<int> vt_int;
typedef vector<char> vt_char;

template<typename T1,typename T2> inline bool ckmin(T1 &a,T2 b){
	if(a>b){
		a=b;
		return true;
	}
	return false;
}
template<typename T1,typename T2> inline bool ckmax(T1 &a,T2 b){
	if(a<b){
		a=b;
		return true;
	}
	return false;
}

namespace smart_math{
    long long quickpow(long long a,long long b,long long mod=0){
        long long ret=1;
        while(b){
            if(b&1)ret*=a;
            if(mod)ret%=mod;
            b>>=1;
            a*=a;
            if(mod)a%=mod;
        }
        if(mod)ret%=mod;
        return ret;
    }
    long long quickmul(long long a,long long b,long long mod=0){
    	long long ret=0;
    	while(b){
    		if(b&1)ret+=a;
    		if(mod)ret%=mod;
    		b>>=1;
    		a=a+a;
    		if(mod)a%=mod;
		}
		if(mod)ret%=mod;
		return ret;
	}
	long long ceil_x(long long a,long long b){
		if(a%b==0)return a/b;
		else return (a/b)+1;
	}
}
using namespace smart_math;
const long long mod=1e9+7;
const long long N=310000;
const long long M=300;

int dp[60][60][60];
int dfs(int n,int m,int k){
	if(n*m==k||k==0)return 0;
	if(n>m)swap(n,m);
	if(dp[n][m][k])return dp[n][m][k];
	
	int minn=mod;
	for(int i=1;i<=n/2;i++){
		for(int j=0;j<=k;j++){
			int ans=m*m+dfs(i,m,j)+dfs(n-i,m,k-j);
			ckmin(minn,ans);
		}
	}
	
	for(int i=1;i<=m/2;i++){
		for(int j=0;j<=k;j++){
			int ans=n*n+dfs(i,n,j)+dfs(m-i,n,k-j);
			ckmin(minn,ans);
		}
	}
	return dp[n][m][k]=minn;
}
int solve(){
	int n,m,k;
	cin>>n>>m>>k;
	cout<<dfs(n,m,k)<<endl;
	
    return 0;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    t=1;
    cin>>t;
    while(t--){
        int flag=solve();
        if(flag==1) YES;
        if(flag==-1) NO;
    }
    return 0;
}

标签:Bar,int,long,Chocolate,return,Problem,define,dp,mod
From: https://www.cnblogs.com/jiangXxin/p/17865429.html

相关文章

  • Problem: B. Queries on a String
    题意简述:给出一个字符串,每次给定l,r,k,选择一个子串l-r,然后子串向右移动k个单位.做法:每次k对子串的长度取模,然后模拟即可(使用substr函数截取前半段和后半段,交换前半段和后半段即可)点击查看代码//Problem:B.QueriesonaString//Contest:Codeforces-EducationalCo......
  • Problem: A. Tricky Sum
    A:做法:数据比较小,用求和公式(n+1)*n/2,减去所有2的幂即可点击查看代码//Problem:A.TrickySum//Contest:Codeforces-EducationalCodeforcesRound1//URL:https://codeforces.com/contest/598/problem/A//MemoryLimit:256MB//TimeLimit:1000ms//Aut......
  • 论文:FEED-FORWARD NETWORKS WITH ATTENTION CAN SOLVE SOME LONG-TERM MEMORY PROBLEM
    题目:FEED-FORWARDNETWORKSWITHATTENTIONCANSOLVESOMELONG-TERMMEMORYPROBLEMS”(Raffel和Ellis,2016,p.1)“带有注意力的前馈网络可以解决一些长期记忆问题”(Raffel和Ellis,2016,p.1)(pdf)这篇论文提出了一种适用于前馈神经网络的简化注意力模型,并展示了......
  • QToolBar右侧添加QAction
    使用QToolBar的addWidget,添加一个可伸缩的空QWidget//Action放右侧:使用QToolBar的addWidget,添加一个可伸缩的空QWidget。QWidget*spacer=newQWidget;spacer->setSizePolicy(QSizePolicy::Expanding,QSizePolicy::Expanding);ui->toolBar->addWidget(spacer);//之后的QActi......
  • The Design of Feedback Control Systems--Advanced Problems
    AP10.1Athree-axispick-and-placeapplicationrequirestheprecisemovementofaroboticarminthree-dimensionalspace,asshowninFigureAP10.1forjoint2.Thearmhasspecificlinearpathsitmustfollowtoavoidotherpiecesofmachinery.Theovers......
  • [ABC315Ex] Typical Convolution Problem
    题目链接首先观察到这个形式,容易发现它和常规的卷积不同点就在于:题目给出的求和定义中,\(\sum\)符号下面的式子是\(i+j<N\)求和而不是\(i+j=N\)。为了方便计算,我们引入:\[G_n=\sum_{i+j<N}F_iF_j\]我们发现,假设所有\(F_{1\sim{i-1}}\)已经求解完毕了,那么我们就可以通过之......
  • 2023 合肥站 热身赛 B Problem F. Flower’s Land 换根dp 依赖背包
    传送门。求出包含某个点连通块大小为K的权值和最大值。钦定1为根节点,只求根节点的答案,其实是一个依赖性01背包问题可以\(nk\)的时间内解决。考虑进行换根操作,由于背包是取max的背包没办法进行背包的删除,然而取前后缀背包背包的合并为\(k^2\)复杂度过高。当时还有一个想法是点......
  • [ABC327G] Many Good Tuple Problems
    题目链接简化题意:有一个\(n\)个点的图,问有多少个长度为\(M\)的边序列,满足连边后图是二分图。\(n\le30,m\le10^9\)考虑先强制要求无重边。定义\(f_{i,j}\)为\(i\)个点,\(j\)条边的图的二分图染色数量(染色方式不同算多次)。这个是可以通过枚举黑色点的数量算出来。然......
  • OI_problem 玛丽卡_洛谷P1186
    题意一个\(N\)个点\(M\)条边的带边权无向图,要求输出最小的\(V\)使得不管去掉哪一条边,都存在从\(1\)到\(n\)的路径使得边权和不超过\(V\)。思路感觉朴素不太好做,考虑二分。对于一个二分值,即要判断在关于这个值的生成图中,\(1\)和\(n\)在不在一个边双里。考......
  • 无涯教程-Tk - Scrollbar部件函数
    滚动条小部件是无需文本或画布小部件即可工作的滚动小部件。滚动条小部件的语法如下所示。scrollbarscrollbarNameoptionsScrollbar-参数下表列出了可用于滚动条小部件的选项。Sr.No.Syntax&Remark1-backgroundcolor用于设置小部件的背景颜色。2-borderwidt......