• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

education round #1 E. Chocolate Bar

开发技术 开发技术 6天前 7次浏览

给出一块 (ntimes m) 的巧克力,想恰好吃到 (k) 块巧克力 ,也就是吃到巧克力的面积为 (k) .

如果沿水平方向把大小为 (atimes b) 的巧克力掰成两半,需要代价 (b^2) .

如果沿竖直方向把大小为 (atimes b) 的巧克力掰成两半,需要代价 (a^2) .

求需要的最小代价 . 有 (t) 组询问.

(1leq tleq 40910)

(1leq n,mleq 30, 1leq kleq min(ncdot m,50))

(dp(i,j,k)) 表示大小为 (itimes j) 的巧克力,最后迟到 (k) 块巧克力的最小代价.

(dp) 转移方程为 :

(dp(i,j,k)=minlimits_{0leq yleq k}(minlimits_{1<x<i}dp(x,j,y)+dp(i-x,j,k-y),minlimits_{1<x<j} (dp(i,x,y)+dp(i,j-x,k-y)))).

我第一想到的使用记忆化搜索,但是,t 了,其实时间复杂度是对的,只是 dfs 搜索函数调用叠加需要的时间过大,常数也过大,所以会 t.

如果直接枚举的话,在 cf 跑了 171 ms.

有的时候记忆化搜索会避免一些不需要的状态,但是在时间复杂度卡得很紧,并且可用状态较多时,记忆化搜索不是一个好选择 . 本题,直接枚举和记忆化搜索几乎是 10 倍的差距.

时间复杂度 : (O((n+m)nmk))

空间复杂度 : (O(nmk))

第一次提交 : Time limited exceed on test 3

code

#include<bits/stdc++.h>
using namespace std;
const int inf=1e9+10;
int t;
int n,m,s;
int dp[32][32][52];
inline void upd(int &x,int y){x=min(x,y);}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	for(int i=0;i<32;i++)for(int j=0;j<32;j++)for(int k=1;k<52;k++)dp[i][j][k]=inf;
	for(int i=1;i<32;i++)for(int j=1;j<32;j++){
		dp[i][j][0]=0;
		if(i*j<=50)dp[i][j][i*j]=0;
	}
	for(int i=1;i<=30;i++)for(int j=1;j<=30;j++)for(int k=0;k<=50;k++){
		for(int x=0;x<=k;x++){
			for(int y=1;y<i;y++)upd(dp[i][j][k],dp[y][j][x]+dp[i-y][j][k-x]+j*j);
			for(int y=1;y<j;y++)upd(dp[i][j][k],dp[i][y][x]+dp[i][j-y][k-x]+i*i);
		}
	} 
	cin>>t;
	while(t--){
		cin>>n>>m>>s;
		cout<<dp[n][m][s]<<endl;
	}	
	return 0;
}
/*inline? ll or int? size? min max?*/


程序员灯塔
转载请注明原文链接:education round #1 E. Chocolate Bar
喜欢 (0)