正文

[noi1999]棋盘分割（推式子+dp）

安  安  2022-09-22  709

关键词：

http://poj.org/problem?id=1191

棋盘分割

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 15655		Accepted: 5556

Description

将一个８*８的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了(n-1)次后，连同最后剩下的矩形棋盘共有n块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行)

原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘，并使各矩形棋盘总分的均方差最小。
均方差

，其中平均值

，x_i为第i块矩形棋盘的总分。
请编程对给出的棋盘及n，求出O'的最小值。

Input

第1行为一个整数n(1 < n < 15)。
第2行至第9行每行为8个小于100的非负整数，表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。

Output

仅一个数，为O'（四舍五入精确到小数点后三位）。

Sample Input

3
1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0
1 1 1 1 1 1 0 3

Sample Output

1.633

Source

Noi 99

/*
设f(i,a,b,c,d)表示切第i刀，剩余的矩形左上角和右下角的坐标是(a,b)和(c,d)，
除了剩余部分其它部分的xi平方和的最小值。
那么f(i)可以向f(i+1)转移，只需要暴力枚举第i+1刀从哪里切了一刀即可。 
*/ 
#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;
const int inf=1<<30;
int n, chess[9][9],sum[9][9],dp[9][9][9][9][15];

int getX(int y1, int x1, int y2, int x2)
{
    int a=sum[y2][x2]-sum[y2][x1-1]-sum[y1-1][x2]+sum[y1-1][x1-1];
    return a*a;
}
int main()
{
    scanf("%d", &n);
    for(int i=1; i<=8; i++)
        for(int j=1; j<=8; j++)
            scanf("%d", &chess[i][j]);
    for(int i=1; i<=8; i++)
    {
        for(int j=1; j<=8; j++)
            sum[i][j]=sum[i][j-1]+chess[i][j];
        for(int j=1; j<=8; j++)
            sum[i][j]+=sum[i-1][j];
    }

    for(int i1=1; i1<=8; i1++)
      for(int j1=1; j1<=8; j1++)
        for(int i2=i1; i2<=8; i2++)
          for(int j2=j1; j2<=8; j2++)
            dp[i1][j1][i2][j2][0]=getX(i1, j1, i2, j2);

    for(int i=1; i<n; i++)
      for(int i1=1; i1<=8; i1++)
        for(int j1=1; j1<=8; j1++)
          for(int i2=i1; i2<=8; i2++)
            for(int j2=j1; j2<=8; j2++)
            {
                dp[i1][j1][i2][j2][i]=inf;
                //左右切割
                for(int k=j1; k<j2; k++)
                  dp[i1][j1][i2][j2][i]=min(dp[i1][j1][i2][j2][i], min(dp[i1][j1][i2][k][i-1]+dp[i1][k+1][i2][j2][0], dp[i1][j1][i2][k][0]+dp[i1][k+1][i2][j2][i-1]));
                //上下切割
                for(int k=i1; k<i2; k++)
                  dp[i1][j1][i2][j2][i]=min(dp[i1][j1][i2][j2][i], min(dp[i1][j1][k][j2][i-1]+dp[k+1][j1][i2][j2][0], dp[i1][j1][k][j2][0]+dp[k+1][j1][i2][j2][i-1]));
            }
    printf("%d\n",dp[1][1][8][8][n-1]);
    return 0;
}

poj1991noi1999棋盘分割

棋盘分割TimeLimit:1000MS MemoryLimit:10000KTotalSubmissions:15581 Accepted:5534Description将一个８*８的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了(n-1)次后，连同最后... 查看详情

bzoj1867:[noi1999]钉子和小球（dp）

　　一眼题...输出分数格式才是这题的难点QAQ　　学习了分数结构体...#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<algorithm>#definelllonglongusingnamespacestd;constintmax 查看详情

bzoj1867:[noi1999]钉子和小球dp(代码片段)

设f[i][j]为掉到f[i][j]时的概率然后分情况随便转移一下就好主要是要手写分数比较麻烦#include<iostream>#include<cstdio>usingnamespacestd;constintN=55;intn,m;chara[N][N];longlonggcd(longlonga,longlongb)return!b?a:gcd(b,a%b);s 查看详情

poj1191棋盘分割区间dp记忆化搜索(代码片段)

棋盘分割TimeLimit: 1000MS MemoryLimit: 10000KTotalSubmissions: 16263 Accepted: 5812Description将一个８*８的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了(n-... 查看详情

bzoj千题计划189：bzoj1867:[noi1999]钉子和小球

http://www.lydsy.com/JudgeOnline/problem.php?id=1867 dp[i][j]落到（i，j）的方案数dp[i][j]=0.5*dp[i-1][j] [(i-1,j)位置有钉子]+0.5*dp[i-1][j-1] [（i-1.j-1）位置有钉子]+dp[i-1][j-2] [（i-1，j-2）查看详情

poj1191棋盘分割（区间dp）题解(代码片段)

题意：中文题面思路：不知道直接暴力枚举所有情况行不行。。。我们可以把答案转化为所以答案就是求xi2的最小值，那么我们可以直接用区间DP来写。设dp[x1][y1][x2][y2][k]为x1y1到x2y2区间分割为k份的最下平方和，显然k=1是就是区... 查看详情

递归3--棋盘分割

递归3--棋盘分割一、总结：怎么写出递推公式（完成百分之90）：尝试分割，分析来源去向，从分析f(n)的时候注意分析f(n-1)记录表法（解决超时问题）二、题目分析及代码：查看详情

[sdoi2016]征途(代码片段)

嘟嘟嘟这题跟[APIO2014]序列分割极像，做法也几乎相同。首先令$dp[i][j]$表示前$i$个数分为$j$段的最小方差，转移方程也很简单，就是枚举和上一段的分割位置。唯一恶心的就是化简式子。大力推方差式子后，得出了这个东西... 查看详情

sequence——强行推式子+组合意义(代码片段)

...F(x-1))*x贡献到答案里n平方的做法可以直接DP，感觉有式子可言，就推出式子：类似coat，每个长度为i的计算i次。再容斥下：F是方案数，还是求：枚举分成的段数，枚举多少个超过i进行容斥：突破口：有个n-i*k-1，意味着... 查看详情

poj1191棋盘分割（区间dp，记忆化搜索）

题面思路：分析公式，我们可以发现平均值那一项和我们怎么分的具体方案无关，影响答案的是每个矩阵的矩阵和的平方，由于数据很小，我们可以预处理出每个矩阵的和的平方，执行状态转移。设dp[l1][r1][l2][r2][k]是矩阵l1,r1,l2,... 查看详情

概率dp——逆推期望+循环迭代zoj3329(代码片段)

...发现每一项都和dp[0]相关，那我们将dp[i]设为和dp[0]有关的式子dp[i]=a[i]*dp[0]+b[i],然后再回代到原来的期望方程里然后进行整理，可以发现两个系数a[i],b[i]是可以逆推的，并且通过求出a[0],b[0]可以求出dp[0]#include<bits/stdc++.h>usingna... 查看详情

推式子小技巧

推式子小技巧标签（空格分隔）：数学先讲一些万金油交换求和顺序，这个很(naive)。式子可以随意提到与其无关的枚举项前后，这个也很(naive)。算贡献思想，这个非常重要，一般需要一点个人能力，只要转化前后每一项被算的... 查看详情

noi4_1_1999[日志排序]

复杂的判断&多余的空格=n个wronganswertypeevent=recordst:string[100];year,mon,day,hour,min,sec,lse:integer;t:longint;end;vara:array[1..10000]ofevent;n:longint;functionbigger(i,j:integer):boolean;beginifa[i].ye 查看详情

[noi1999]生日蛋糕

题目：洛谷P1731、VijosP1297、codevs1710。题目大意：让你做一个体积为$Npi$的每层都是圆柱的蛋糕，m层，且从下到上每层的高度和半径都不超过下面一层的，且是整数。设表面积Q=$Spi$，问你最小的S是多少（不可能输出0）。解题思... 查看详情

noi1999生日蛋糕

https://www.luogu.org/problem/show?pid=1731题目背景7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。设从下往上数第i(1<=i<=M)层蛋糕是半径为Ri,高度为Hi的圆柱。当i<M时，要求Ri>Ri+1且Hi>... 查看详情

noi题库8465

...象棋以日字形规则移动。请编写一段程序，给定n*m大小的棋盘，以及马的初始位置(x，y)，要求不能重复经过棋盘上的同一个点，计算马可以有多少途径遍历棋盘上的所有点。输入第一行为整数T(T<10)，表示测试数据组数。每一... 查看详情

hdu1024最大m字段和

...完题之后感觉很简单但就是写不来，后来仿佛推到一个dp式子了，对，仿佛...然后抄袭了个式子，嘿，和我的式子大体相似，然后就是很玄学的优化了...不多瞎bb了1.首先，定义数组num[n],dp[m][n].num[n]用来存储n个整数组成的序列.dp[... 查看详情

bzoj3672[noi2014]购票

推一下式子发现就是普通的斜率优化，但是放到了树上，那么我们怎么做呢，树上有什么能保证复杂度的求路径的算法呢，点分治！但是这是有根树，我们对于首先处理点分治后的重心以及与根相连的那个块，之后我们将块中剩... 查看详情