POJ--1191[棋盘分割] 记忆化搜索___简言的博客-程序员秘密

技术标签: 算法  POJ  DP  解题报告  

思路:(具体参考《算法艺术与信息学竞赛》)

1,先化简均方差公式,可以看出,只需要让每个分割后的矩形的总分的平方和尽量小,即可使均方差最小。

2,考虑左上角坐标为(x1,y1),右下角坐标为(x2,y2)的棋盘,设它的总和为s[x1,y1,x2,y2]切割k次以后得到k+1块矩形的总分平方和最小值为d[k,x1,y1,x2,y2],则它可以沿着横线切,也可以沿着竖线切,然后选一块继续切(递归)。。

3,由1,2部可以得到状态转移方程:
d[k,x1,y1,x2,y2]=
min{
min{d[k-1,x1,y1,a,y2]+s[a+1,y1,x2,y2]^2,d[k-1,a+1,y1,x2,y2]+s[x1,y1,a,y2]^2},
min{d[k-1,x1,y1,x2,b]+s[x1,b+1,x2,y2]^2,d[k-1,x1,b+1,x2,y2]+s[x1,y1,x2,b]^2}
}其中:(x1<=a<x2),(y1<=b<y2);初始值,对于k==0,d[k,x1,y1,x2,y2]=s[x1,y1,x2,y2]^2;

 

 

CODE:

/*记忆化搜索*/
/*AC代码:0ms*/
#include <iostream>
#include <cmath>
#define INF 99999999//这里不能用0x7fffffff会溢出而WA
#define min(a,b) (a<b?a:b)
int s[9][9];//s[i][j]记录(1,1)-(i,j)中所有元素的和
int dp[16][9][9][9][9];
int N;
double ave;
void get_s()
{
	int i,j,temp,v;
	memset(s,0,sizeof(s));
	memset(dp,-1,sizeof(dp));
	for(i=1;i<=8;i++)
	{
		for(j=1,temp=0;j<=8;j++)
		{
			scanf("%d",&v);
			temp+=v;
			s[i][j]=temp;
			if(i>1) s[i][j]+=s[i-1][j];
		}
	}
	ave=((double)s[8][8])*1.0/N;
}
int get_sum(int x1,int y1,int x2,int y2)
{
	int ans=0;
	ans+=s[x2][y2];
	if(x1>1) ans-=s[x1-1][y2];
	if(y1>1) ans-=s[x2][y1-1];
	if(x1>1&&y1>1) ans+=s[x1-1][y1-1];
	return ans*ans;//关键
}
int dfs(int k,int x1,int y1,int x2,int y2)
{
	int i,w1,w2,temp;
	if(dp[k][x1][y1][x2][y2]!=-1) return dp[k][x1][y1][x2][y2];
	if(k==1) 
	{
		dp[k][x1][y1][x2][y2]=get_sum(x1,y1,x2,y2);
		return dp[k][x1][y1][x2][y2];
	}
	int ans=INF;
	for(i=x1;i<x2;i++)//水平切割
	{
		w1=dfs(k-1,x1,y1,i,y2)+get_sum(i+1,y1,x2,y2);
		w2=dfs(k-1,i+1,y1,x2,y2)+get_sum(x1,y1,i,y2);
		temp=min(w1,w2);
		ans=min(ans,temp);
	}
	for(i=y1;i<y2;i++)
	{
		w1=dfs(k-1,x1,y1,x2,i)+get_sum(x1,i+1,x2,y2);
		w2=dfs(k-1,x1,i+1,x2,y2)+get_sum(x1,y1,x2,i);
		temp=min(w1,w2);
		ans=min(ans,temp);
	}
	dp[k][x1][y1][x2][y2]=ans;
	return ans; 
}
int main()
{
	while(scanf("%d",&N)!=EOF)
	{
		get_s();
		int ans=dfs(N,1,1,8,8);
		//printf("%d %.3lf\n",ans,ave);
		double res=((double)ans)*1.0/N-ave*ave;
		printf("%.3lf\n",sqrt(res));
	}
return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/allenjy123/article/details/6646563

智能推荐

HTML5 - Web存储使用详解(本地存储、会话存储)_飞鹰再现的博客-程序员秘密_本地存储和会话存储的异同

1,Web存储介绍HTML5的Web存储功能是让网页在用户计算机上保存一些信息。Web存储又分为两种:(1)本地存储,对应 localStorage 对象。用于长期保存网站的数据,并且站内任何页面都可以访问该数据。(2)会话存储,对应 sessionStorage 对象。用于临时保存针对一个窗口(或标签页)的数据。在访客关闭窗口或者标签页之前,这些数据是存在的,而关闭之后就

Bootstrap fileinput上传图片到fastdfs_周星星_9527的博客-程序员秘密

参考链接:https://github.com/kartik-v/bootstrap-fileinputhttp://www.cnblogs.com/landeanfen/p/5007400.html前面大神已经把过程写得很清楚了,但我还是把我实践的过程记录一下。1、引入Bootstrap fileinput1.1 引入必要css、js&amp;amp;lt;link href=&amp;quot;/css/boo...

unity创建资源文件ScriptableObject_迷失的犬的博客-程序员秘密_unity 新增资源文件

他和一般的脚本一样,但是他不是包涵在MonoBehaviour下,而是在ScriptableObject中如using System.Collections;using System.Collections.Generic;using UnityEngine;[CreateAssetMenu(fileName ="New Date",menuName ="Character Stats/Date")]public class CharacterData_SO : ScriptableOb

jupyter notebook报错500 : Internal Server Error_weixin_46772722的博客-程序员秘密

打开cmd输入:pip install --upgrade --user nbconvert在重新打开jupyter即可

前端小玩意儿:用three.js开发的手机太空穿越VR游戏,特效非常猛哦_coder吹雪的博客-程序员秘密_前端可以开vr游戏吗

hello,今天给大家用three.js开发了一个手机太空穿越VR游戏,确实不容易,小编的头发又少了一大截。Ok,废话少说,先看效果。一、效果图&lt;!DOCTYPE html&gt;&lt;html lang="en" &gt;&lt;head&gt;&lt;meta charset="UTF-8"&gt;&lt;title&gt;Three.js Mobile VR Sonic&lt;/title&gt;&lt;link rel="stylesheet" href="css/s

Linux的completions同步机制_newand的博客-程序员秘密

1. 什么是completions机制?在内核编程中常有这样的场景,在当前线程中创建一个线程,并且等待它完成之后再继续执行。通常可以用信号量来解决它,也可以用completion机制来解决。2. 为什么用completions ,它比信号量好在哪?使用completion比使用信号量简单。使用completion可以一次性唤醒所有等待进程,而用信号量会比较麻烦。 The b

随便推点

在b-s开发中经常用到的javaScript技术 _xifo的博客-程序员秘密

一、验证类 1、数字验证内   1.1 整数   1.2 大于0的整数 (用于传来的ID的验证)   1.3 负整数的验证   1.4 整数不能大于iMax   1.5 整数不能小于iMin 2、时间类   2.1 短时间,形如 (13:04:06)   2.2 短日期,形如 (2003-12-05)   2.3 长时间,形如 (2003-12-05 13:04:06)   2.4 只有年和月。形

第一章-----操作系统导论_飘过的小熊的博客-程序员秘密_操作系统导论

第一章—–操作系统导论标签(空格分隔): 操作系统之哲学原理

CC++程序训练6---歌德巴赫猜想的证明_Du_Chunfeng的博客-程序员秘密_输入一个不小于6的偶数n

Problem Description验证“每个不小于6的偶数都是两个素数之和”,输入一个不小于6的偶数n,找出两个素数,使它们的和为n。Input输入一个不小于6的偶数n。Output找出两个素数,使它们的和为n。只需要输出其中第一个素数最小的一组数据即可。Example Input80Example Output80=7+73#include &amp;lt;stdio.h&amp;gt;...

计算机美术设计基础教案,电脑美术美术教案_weixin_39861918的博客-程序员秘密

本节课进步的地方:1、在设计中体现了综合性和多样性,在美术教学中融入了音乐,还准备在以后教学中融入电脑教学,运用计算机的绘图软件绘画。2、在课件的制作中对音乐和图片的选择有较强的视觉和听觉冲击力。3、在语言讲解上较以前精练简洁。4、在教学仪态上较以前少了些随便的感觉,多了些亲切的感觉。要改进的地方:...篇一:电脑美术教学反思从这节课中,可以开出学生在课堂中积极主动,课堂气氛活跃,学生敢于发言,富...

【机器学习系列】概率图模型第一讲:从概率和图的角度理解概率图模型_CHEONG_KG的博客-程序员秘密

作者:CHEONG公众号:AI机器学习与知识图谱研究方向:自然语言处理与知识图谱前言: 文中含有大量公式,若需获取本文全部的手书版原稿资料,扫码关注公众号【AI机器学习与知识图谱】,回复: 概率图模型第一讲 即可获取。可添加微信号【17865190919】进公众号讨论群,加好友时备注来自CSDN。原创不易,转载请告知并注明出处!让我们进入正文。本文将从从概率和图两个角度先来理解一下概率图模型。一、概率角度首先从概率的角度看,概率问题关注什么?随机变量x服从何种概率分布,对于高维随机变量p..

推荐文章

热门文章

相关标签