前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >POJ-1191-棋盘分割(动态规划)

POJ-1191-棋盘分割(动态规划)

作者头像
ShenduCC
发布2018-04-25 17:24:36
9050
发布2018-04-25 17:24:36
举报
文章被收录于专栏:算法修养

棋盘分割 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 13593 Accepted: 4846 Description

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

原棋盘上每一格有一个分值,一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘,并使各矩形棋盘总分的均方差最小。 均方差,其中平均值,xi为第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

总结出来状态转移方程,这道题目就好解决了, 状体转移方程 横着切x轴 dp[k][x1][y1][x2][y2]=min(dp[k][x1][y1][x2][y2], dp[0][x1][y1][t][y2]+dp[k-1][t+1][y1][x2][y2]); dp[k][x1][y1][x2][y2]=min(dp[k][x1][y1][x2][y2], dp[k-1][x1][y1][t][y2]+dp[0][t+1][y1][x2][y2]) 竖着切y轴 dp[k][x1][y1][x2][y2]=min(dp[k][x1][y1][x2][y2], dp[0][x1][y1][x2][t]+dp[k-1][x1][t+1][x2][y2]); dp[k][x1][y1][x2][y2]=min(dp[k][x1][y1][x2][y2], dp[k-1][x1][y1][x2][t]+dp[0][x1][t+1][x2][y2]);

代码语言:javascript
复制
#include <iostream>
#include <algorithm>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

using namespace std;
#define MAX 99999999
int a[10][10];
double dp[15][10][10][10][10];//一个矩形的两个顶点和切割了几次
int num[10][10];
int res;
double sum(int x1,int y1,int x2,int y2)
{
    double ans=(double)(num[x2][y2]-num[x2][y1-1]-num[x1-1][y2]+num[x1-1][y1-1]);
    return ans*ans;
}
int main()
{
   int n;
    while(scanf("%d",&n)!=EOF)
    {
        memset(num,0,sizeof(num));
        res=0;
        for(int i=1;i<=8;i++)
        {
            for(int j=1;j<=8;j++)
            {
                scanf("%d",&a[i][j]);
                num[i][j]=(num[i-1][j]+num[i][j-1]-num[i-1][j-1]+a[i][j]);
                res+=a[i][j];
            }
        }
        //数组初始化
        for(int x1=1;x1<=8;x1++)
            for(int y1=1;y1<=8;y1++)
                for(int x2=x1;x2<=8;x2++)
                   for(int y2=y1;y2<=8;y2++)
                      dp[0][x1][y1][x2][y2]=sum(x1,y1,x2,y2);
        for(int k=1;k<n;k++)
        {
             for(int x1=1;x1<=8;x1++)
             {
                  for(int y1=1;y1<=8;y1++)
                  {
                       for(int x2=x1;x2<=8;x2++)
                       {
                           for(int y2=y1;y2<=8;y2++)
                            {
                                dp[k][x1][y1][x2][y2]=MAX;
                                for(int t=x1;t<x2;t++)
                                {
                                    dp[k][x1][y1][x2][y2]=min(dp[k][x1][y1][x2][y2],dp[0][x1][y1][t][y2]+dp[k-1][t+1][y1][x2][y2]);
                                    dp[k][x1][y1][x2][y2]=min(dp[k][x1][y1][x2][y2],dp[k-1][x1][y1][t][y2]+dp[0][t+1][y1][x2][y2]);
                                }
                                for(int t=y1;t<y2;t++)
                                {
                                    dp[k][x1][y1][x2][y2]=min(dp[k][x1][y1][x2][y2],dp[0][x1][y1][x2][t]+dp[k-1][x1][t+1][x2][y2]);
                                    dp[k][x1][y1][x2][y2]=min(dp[k][x1][y1][x2][y2],dp[k-1][x1][y1][x2][t]+dp[0][x1][t+1][x2][y2]);
                                }
                            }
                       }
                  }
             }
        }


        double ans1=dp[n-1][1][1][8][8]*1.0/n-((double)res*1.0/n)*((double)res*1.0/n);
        double ans2=sqrt(ans1);

        printf("%.3f\n",ans2);
    }
    return 0;
}

再给一个自己写的记忆化搜索的代码

代码语言:javascript
复制
#include <iostream>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <stdlib.h>
#include <stdio.h>

using namespace std;
#define MAX 9999999
int dp[15][9][9][9][9];
int a[9][9];
int vis[15][9][9][9][9];
int n;
int ans;

int sum(int x1,int y1,int x2,int y2)
{
    int res=0;
    for(int i=x1;i<=x2;i++)
    {
        for(int j=y1;j<=y2;j++)
        {
            res+=a[i][j];
        }
    }
    return res;
}
int dfs(int x1,int y1,int x2,int y2,int n)
{
    if(vis[n][x1][y1][x2][y2]!=-1)
        return vis[n][x1][y1][x2][y2];
    vis[n][x1][y1][x2][y2]=MAX;

    //横切
    if(x1<x2)
    {
        for(int k=x1;k<x2;k++)
        {
            vis[n][x1][y1][x2][y2]=min(vis[n][x1][y1][x2][y2],dfs(x1,y1,k,y2,0)+dfs(k+1,y1,x2,y2,n-1));
            vis[n][x1][y1][x2][y2]=min(vis[n][x1][y1][x2][y2],dfs(x1,y1,k,y2,n-1)+dfs(k+1,y1,x2,y2,0));
        }

    }
    if(y1<y2)
    {
        for(int k=y1;k<y2;k++)
        {
            vis[n][x1][y1][x2][y2]=min(vis[n][x1][y1][x2][y2],dfs(x1,y1,x2,k,0)+dfs(x1,k+1,x2,y2,n-1));
            vis[n][x1][y1][x2][y2]=min(vis[n][x1][y1][x2][y2],dfs(x1,y1,x2,k,n-1)+dfs(x1,k+1,x2,y2,0));
        }

    }


    return vis[n][x1][y1][x2][y2];
}
int main()
{
    int num;
    while(scanf("%d",&n)!=EOF)
    {
        num=0;
        for(int i=1;i<=8;i++)
        {
            for(int j=1;j<=8;j++)
            {
                scanf("%d",&a[i][j]);
                num+=a[i][j];
            }
        }
        //memset(vis,-1,sizeof(vis));
        for(int x1=1;x1<=8;x1++)
            for(int y1=1;y1<=8;y1++)
                for(int x2=x1;x2<=8;x2++)
                    for(int y2=y1;y2<=8;y2++)
                        for(int k=0;k<=n-1;k++)
                         {
                             if(k==0)
                             {
                              int term=sum(x1,y1,x2,y2);
                              vis[0][x1][y1][x2][y2]=term*term;
                             }
                             else
                                 vis[k][x1][y1][x2][y2]=-1;
                         }

        int ans=dfs(1,1,8,8,n-1);

        double ans1=ans*1.0/n-((double)num*1.0/n)*((double)num*1.0/n);
        double ans2=sqrt(ans1);
        printf("%.3f\n",ans2);

    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2015-12-20 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档