关键词：
http://172.20.6.3/Problem_Show.asp?id=1289
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 using namespace std; 8 int n; 9 int a[10][10]={}; 10 double f[20][10][10][10][10]={}; 11 bool vis[20][10][10][10][10]={}; 12 int main(){ 13 scanf("%d",&n); 14 for(int i=1;i<=8;i++){ 15 for(int j=1;j<=8;j++){ 16 scanf("%d",&a[i][j]); 17 a[i][j]+=a[i][j-1]; 18 a[i][j]+=a[i-1][j]; 19 a[i][j]-=a[i-1][j-1]; 20 } 21 } 22 for(int i=1;i<=8;i++){ 23 for(int j=1;j<=8;j++){ 24 for(int w=i;w<=8;w++){ 25 for(int q=j;q<=8;q++){ 26 f[1][i][j][w][q]=1.0*(a[w][q]-a[i-1][q]-a[w][j-1]+a[i-1][j-1]); 27 f[1][i][j][w][q]*=f[1][i][j][w][q];vis[1][i][j][w][q]=1; 28 } 29 } 30 } 31 } 32 double ro=1.0*a[8][8]/(1.0*n); 33 ro=ro*ro; 34 for(int k=2;k<=n;k++){ 35 for(int i=1;i<=8;i++){ 36 for(int j=1;j<=8;j++){ 37 for(int w=i;w<=8;w++){ 38 for(int q=j;q<=8;q++){ 39 for(int z=i;z<w;z++){ 40 if((vis[k-1][i][j][z][q]&&vis[1][z+1][j][w][q])&&(vis[k][i][j][w][q]==0||f[k][i][j][w][q]-(f[k-1][i][j][z][q]+f[1][z+1][j][w][q])>0)){ 41 f[k][i][j][w][q]=f[k-1][i][j][z][q]+f[1][z+1][j][w][q];vis[k][i][j][w][q]=1; 42 } 43 if((vis[1][i][j][z][q]&&vis[k-1][z+1][j][w][q])&&(vis[k][i][j][w][q]==0||f[k][i][j][w][q]-(f[1][i][j][z][q]+f[k-1][z+1][j][w][q])>0)){ 44 f[k][i][j][w][q]=f[1][i][j][z][q]+f[k-1][z+1][j][w][q];vis[k][i][j][w][q]=1; 45 } 46 } 47 for(int z=j;z<q;z++){ 48 if((vis[k-1][i][j][w][z]&&vis[1][i][z+1][w][q])&&(vis[k][i][j][w][q]==0||f[k][i][j][w][q]-(f[k-1][i][j][w][z]+f[1][i][z+1][w][q])>0)){ 49 f[k][i][j][w][q]=f[k-1][i][j][w][z]+f[1][i][z+1][w][q];vis[k][i][j][w][q]=1; 50 } 51 if((vis[1][i][j][w][z]&&vis[k-1][i][z+1][w][q])&&(vis[k][i][j][w][q]==0||f[k][i][j][w][q]-(f[1][i][j][w][z]+f[k-1][i][z+1][w][q])>0)){ 52 f[k][i][j][w][q]=f[1][i][j][w][z]+f[k-1][i][z+1][w][q];vis[k][i][j][w][q]=1; 53 } 54 } 55 } 56 } 57 } 58 } 59 } 60 double z=f[n][1][1][8][8]/n-ro; 61 z=sqrt(z); 62 printf("%.3f ",z); 63 return 0; 64 }
poj1991noi1999棋盘分割
棋盘分割TimeLimit:1000MS MemoryLimit:10000KTotalSubmissions:15581 Accepted:5534Description将一个８*８的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了(n-1)次后，连同最后... 查看详情
jzyzoj1390noi2001炮兵阵地状压dp
http://172.20.6.3/Problem_Show.asp?id=1390需要储存该行和上一行两个状态。通过观察规则可以发现条件允许的状态很少（相邻两个至少空两格），据此可以减少状态数量，从而极大压缩空间和时间。代码1#include<iostream>2#include<cstdio&... 查看详情
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） 查看详情
poj百炼——1191棋盘分割(代码片段)
1191:棋盘分割总时间限制:1000ms内存限制:65536kB描述将一个８*８的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了(n-1)次后，连同最后剩下的矩形棋盘共有n块矩... 查看详情
poj1191棋盘分割（区间dp）题解(代码片段)
题意：中文题面思路：不知道直接暴力枚举所有情况行不行。。。我们可以把答案转化为所以答案就是求xi2的最小值，那么我们可以直接用区间DP来写。设dp[x1][y1][x2][y2][k]为x1y1到x2y2区间分割为k份的最下平方和，显然k=1是就是区... 查看详情
jzyzoj1372[noi2002]荒岛野人扩展欧几里得
http://172.20.6.3/Problem_Show.asp?id=1372想法其实很好想，但是我扩展欧几里得还是用得不熟练，几乎是硬套模板，大概因为今天一个下午状态都不大好。扩展欧几里得算法计算的是:ab互质时ax+by=1或ab不互质时ax+by=gcd(a,b)（废话）的一个... 查看详情
jzyzoj1378[noi2002]m号机器人欧拉函数
http://172.20.6.3/Problem_Show.asp?id=1378日常懒得看题目怪不得语文差，要好好读题目了，欧拉函数大概是数论里最友好的了，不用解方程不用转换过来转换过去只需要简单乘在一起就可以了。比较有趣的是求和的部分，因为类似于等比... 查看详情
bzoj1497jzyzoj1344[noi2006]最大获利网络流最大权闭合图
http://www.lydsy.com/JudgeOnline/problem.php?id=1497http://172.20.6.3/Problem_Show.asp?id=1344 思路：（最大权闭合图的思路相同）将所有的用户群获利（正值）作为一个点连一条权值为获利值的边到st点，将所有的建站消耗（输入的是正值但是是... 查看详情
bzoj1562jzyzoj1730cogs409noi2009变换序列二分图匹配
【问题描述】 对于N个整数0,1,……, N-1，一个变换序列T可以将i变成Ti，其中定义x和y之间的距离。给定每个i和Ti之间的距离D(i,Ti)，你需要求出一个满足要求的变换序列T。如果有多个满足条... 查看详情
jzyzoj1388旅游状压dp
http://172.20.6.3/Problem_Show.asp?id=1388 求拓扑排序方案数状压dp，最开始以为是拓扑排序加数论或者搜索，没想到是状压dp，突然气死.jpg；完全没有想到状态转移的方法，syq大佬太神了orz； 写的时候太沉迷与topsort对人顺序的分... 查看详情
jzyzoj1382光棍组织状压dp
http://172.20.6.3/Problem_Show.asp?id=1382 水得过分了，本来以为要用lzx学长的写法写，抱着试试看的想法写了个特暴力的dp+dfs，过了，真是。。。 代码1#include<iostream>2#include<cstdio>3#include<cstring>4#include<algorit 查看详情
jzyzoj1384种花小游戏状压dp
http://172.20.6.3/Problem_Show.asp?id=1384 最开始以为是dfs然后超时了，然后调了半天调成dp，还不如再写一遍。。。代码1#include<iostream>2#include<cstdio>3#include<cstring>4#include<algorithm>5#include<cma 查看详情
poj1191棋盘分割（区间dp，记忆化搜索）
题面思路：分析公式，我们可以发现平均值那一项和我们怎么分的具体方案无关，影响答案的是每个矩阵的矩阵和的平方，由于数据很小，我们可以预处理出每个矩阵的和的平方，执行状态转移。设dp[l1][r1][l2][r2][k]是矩阵l1,r1,l2,... 查看详情
jzyzoj1542[haoi2015]str矩阵乘法dp
http://172.20.6.3/Problem_Show.asp?id=1542dp+矩阵乘法思路hin好想，对于我这种题目稍微学术就几乎什么也不会的人来说唯一的难点在于读题，因为一心想着划水题目没有看清楚，样例wa了一会最后仔细读题发现自己g的操作看错了，非常智... 查看详情
jzyzoj1386扑街状压dp
http://172.20.6.3/Problem_Show.asp?id=1386 有一个W行H列的街道，需要用1*2小砖铺盖，小砖之间互相不能重叠，问有多少种不同的铺法？数组f的不往后延伸指的是没有对后面产生影响的时候的状态，此时这一列的砖可横可竖但是横着的... 查看详情