当前位置:网站首页>321. Chessboard segmentation (2D interval DP)
321. Chessboard segmentation (2D interval DP)
2022-07-02 01:45:00 【seez】
321. Chessboard division - AcWing Question bank
The question :
- A matrix can be crosscut , Or side cutting , As shown in the figure
- For a chessboard cut into two parts , You can and can only select one to continue cutting down
Find the minimum variance , Due to mean square deviation X Fix ,n Fix , What we need to calculate is the area of the divided sub rectangle (xi-X)*(xi-X).
therefore , You can use the search method , Keep raising the minimum
analysis : Two dimensional interval dp, In fact, it is similar to the digital triangle model , Because segmentation may not have a linear recursive relationship , So we use the method of memory search .
- Crosscut i, In two parts [(x1,y1)~(i,y2)],[(i+1,y2)~(x2,y2)]
- Vertical cutting i, In two parts [(x1,y1)~(x2,i)],[(x2,i+1)~(x2,y2)]
initialization : All initialized to infinity , Due to the particularity of planned search , So first initialize to a negative number , Enter to reinitialize
State transition equation / State calculation :
According to the position of cross cutting and vertical cutting i Different , And which subset to continue to divide after division , It can be divided into multiple sets
Crosscut , It is divided into two subsets , Both subsets can be further divided , Another direct calculation
- dp[x1][y1][x2][y2][k]=max(dp[x1][i][x2][y2][k]+sum[x1~i][y1~y2]);
- dp[x1][y1][x2][y2][k]=max(dp[x1][y1][i+1][y2][k]+sum[i+1~]
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N=16;
const int inf=1e9;
int s[N][N];
double dp[N][N][N][N][N];
double X;
double get(int x1,int y1,int x2,int y2)
{
int a=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
return (a-X)*(a-X);
}
double dfs(int x1,int y1,int x2,int y2,int k)
{
double &v=dp[x1][y1][x2][y2][k];// For simplicity , add v
if(v>=0) return v;
if(k==1) return get(x1,y1,x2,y2);
v=1e9; // For the minimum , Initialize to infinity
for(int i=x1;i<x2;i++)
{// Crosscutting subset
v=min(v,dfs(i+1,y1,x2,y2,k-1)+get(x1,y1,i,y2));
v=min(v,dfs(x1,y1,i,y2,k-1)+get(i+1,y1,x2,y2));
}
for(int i=y1;i<y2;i++)
{// Vertically cut subset
v=min(v,dfs(x1,i+1,x2,y2,k-1)+get(x1,y1,x2,i));
v=min(v,dfs(x1,y1,x2,i,k-1)+get(x1,i+1,x2,y2));
}
return v;
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=8;i++)
for(int j=1;j<=8;j++)
cin>>s[i][j];
for(int i=1;i<=8;i++)
for(int j=1;j<=8;j++)
s[i][j]+=s[i][j-1]+s[i-1][j]-s[i-1][j-1];
X=(double)s[8][8]/n;
memset(dp,-1,sizeof dp); // Because the integral may be 0, So take -1
double a=dfs(1,1,8,8,n)/n;
printf("%.3lf",sqrt(a));
return 0;
}
边栏推荐
- Self drawing of menu items and CListBox items
- Single chip microcomputer -- hlk-w801 transplant NES simulator (III)
- How can I batch produce the same title for the video?
- [IVX junior engineer training course 10 papers to get certificates] 01 learn about IVX and complete the New Year greeting card
- GL Studio 5 installation and experience
- 大学的知识是否学而无用、过时?
- 【视频】马尔可夫链蒙特卡罗方法MCMC原理与R语言实现|数据分享
- k线图形态这样记(口诀篇)
- Three core problems of concurrent programming
- Implementation principle of city selector component
猜你喜欢
并发编程的三大核心问题
遷移雲計算工作負載的四個基本策略
Matlab uses resample to complete resampling
The technology boss is ready, and the topic of position C is up to you
Raspberry pie 4B learning notes - IO communication (1-wire)
It's already 30. Can you learn programming from scratch?
Matlab uses audioread and sound to read and play WAV files
How to use a product to promote "brand thrill"?
Penser au jeu 15: penser au service complet et au sous - service
Edge computing accelerates live video scenes: clearer, smoother, and more real-time
随机推荐
Luogu p1775 stone merger (weakened version)
II Basic structure of radio energy transmission system
Based on configured schedule, the given trigger will never fire
三分钟学会基础k线图知识
浅浅了解Servlet
D discard the virtual recovery method
Quatre stratégies de base pour migrer la charge de travail de l'informatique en nuage
MySQL application day02
5g/4g pole gateway_ Smart pole gateway
Laravel artisan 常用命令
Brief introduction to the development of mobile network
This is the form of the K-line diagram (pithy formula)
Liteos learning - first knowledge of development environment
Bat Android Engineer interview process analysis + restore the most authentic and complete first-line company interview questions
开发那些事儿:如何利用Go单例模式保障流媒体高并发的安全性?
Automatically browse pinduoduo products
With the innovation and upgrading of development tools, Kunpeng promotes the "bamboo forest" growth of the computing industry
MPLS experiment operation
How can the tsingsee Qingxi platform play multiple videos at the same time on the same node?
The difference between new and malloc