4.5算法之动态规划 193:棋盘分割 区间dp

题目

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

原棋盘上每一格有一个分值,一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘,并使各矩形棋盘总分的均方差最小。
均方差,其中平均值,xi为第i块矩形棋盘的总分。
请编程对给出的棋盘及n,求出O’的最小值。
输入
第1行为一个整数n(1 < n < 15)。
第2行至第9行每行为8个小于100的非负整数,表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。
输出
仅一个数,为O’(四舍五入精确到小数点后三位)。

思路

区间 dp, dp[k][x1][y1][x2][y2] 表示将,(x1,y1):(x2,y2)区间内的矩形分成 k 块,均方误差的最小值
该问题是一个一对多问题,即两个子矩形的最优解拼接为一个大矩形后不一定为最优解,但是一个大矩形的最优解一定可以由两个子矩形的解拼接而成,所以针对子矩形遍历其横向划分和纵向划分。

其中要最小化平方和即可,具体推导过程参考该博客
https://blog.csdn.net/nnnnnnnnnnnny/article/details/51592665

源码

//
//  193.cpp
//  test
//
//  Created by sgxm on 2020/8/3.
//  Copyright © 2020 sgxm. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <math.h>
#include <memory.h>
#include <iomanip>
#include <string.h>
#define maxn 15
using namespace std;

int dp[15][8][8][8][8];
int s[8][8][8][8];
int tb[8][8];
int n;
int calSum(int x1,int y1,int x2,int y2){
    int sum = 0;
    for(int i = x1;i<=x2;++i){
        for(int j = y1;j <= y2;++j){
            sum+=tb[i][j];
        }
    }
    return sum*sum;
}
int calDp(int k,int x1,int y1,int x2,int y2){
    int MIN = 99999999;

    if(dp[k][x1][y1][x2][y2]!=-1){
        return dp[k][x1][y1][x2][y2];
    }
    if(k == 1){
        return dp[k][x1][y1][x2][y2]=s[x1][y1][x2][y2];
    }
    dp[k][x1][y1][x2][y2]=MIN;
    //横向划分
    for(int x = x1;x<x2;++x){
        int t1 = calDp(k-1, x1, y1, x, y2);
        int t2 = calDp(k-1,x+1,y1,x2,y2);
        int t = min(t1+s[x+1][y1][x2][y2],t2+s[x1][y1][x][y2]);
        MIN = min(MIN,t);
    }
    for(int y = y1;y<y2;++y){
        int t1 = calDp(k-1,x1,y1,x2,y);
        int t2 = calDp(k-1,x1,y+1, x2, y2);
        int t = min(t1+s[x1][y+1][x2][y2],t2+s[x1][y1][x2][y]);
        MIN = min(MIN,t);
    }
    MIN=min(MIN,dp[k][x1][y1][x2][y2]);
    //cout<<k<< " "<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<" = "<<MIN<<endl;
    return  dp[k][x1][y1][x2][y2]=MIN;

}
int main(){
    cin >> n;
    for(int i = 0;i < 8;++i){
        for(int j = 0;j < 8;++j){
            cin >> tb[i][j];
        }
    }
    memset(dp, -1,sizeof(dp));
    //init Sum
    for(int x1 = 0;x1 < 8;++x1){
        for(int y1 = 0;y1 < 8;++y1){
            for(int x2 = x1;x2<8;++x2){
                for(int y2 = y1;y2<8;++y2){
                    s[x1][y1][x2][y2]=calSum(x1,y1,x2,y2);
                }
            }
        }
    }
    //calDp(2,5,5,6,7);
    int sum2 = calDp(n, 0, 0, 7, 7);
    double res = 1.0*n*calDp(n, 0, 0, 7, 7)-s[0][0][7][7];
    cout<<setiosflags(ios::fixed)<<setprecision(3)<<sqrt(res/(n*n))<<endl;
    return 0;
}

4.5算法之动态规划 191:钉子和小球 概率

题目

http://noi.openjudge.cn/ch0405/191/
描述
有一个三角形木板,竖直立放,上面钉着n(n+1)/2颗钉子,还有(n+1)个格子(当n=5时如图1)。每颗钉子和周围的钉子的距离都等于d,每个格子的宽度也都等于d,且除了最左端和最右端的格子外每个格子都正对着最下面一排钉子的间隙。
让一个直径略小于d的小球中心正对着最上面的钉子在板上自由滚落,小球每碰到一个钉子都可能落向左边或右边(概率各1/2),且球的中心还会正对着下一颗将要碰上的钉子。例如图2就是小球一条可能的路径。
我们知道小球落在第i个格子中的概率pi=,其中i为格子的编号,从左至右依次为0,1,…,n。
现在的问题是计算拔掉某些钉子后,小球落在编号为m的格子中的概率pm。假定最下面一排钉子不会被拔掉。例如图3是某些钉子被拔掉后小球一条可能的路径。

输入
第1行为整数n(2 <= n <= 50)和m(0 <= m <= n)。以下n行依次为木板上从上至下n行钉子的信息,每行中’*’表示钉子还在,’.’表示钉子被拔去,注意在这n行中空格符可能出现在任何位置。
输出
仅一行,是一个既约分数(0写成0/1),为小球落在编号为m的格子中的概pm。既约分数的定义:A/B是既约分数,当且仅当A、B为正整数且A和B没有大于1的公因子。

思路

n = 2 时,第 0 层为钉子的上一层,初始小球 2^n
从第 0 层开始,第一个钉子编号为 1,第一个坑位编号为 0,对于每一个坑位考虑
– 其上方钉子空则上两层对应小球数量直接累加
– 左侧钉子不空则左侧钉子上方小球数量一半累加到该位置
– 右侧同理

最后辗转相除法求最大公约数,约分

源码

//
//  191.cpp
//  test
//
//  Created by bytedance on 2020/7/30.
//  Copyright © 2020 bytedance. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
vector<vector<long long>> dp;
vector<vector<char>> cnt;
long long gcd(long long x,long long y){
    return y?gcd(y,x%y):x;
}
int main(){
    long long n,m;
    cin >> n >> m;
    cnt.resize(n+1,vector<char>(n+1));
    dp.resize(n+1,vector<long long>(n+1,0));
    for(long long i = 1;i <= n; ++i){
        for(long long j = 1;j <= i; ++j){
            char c;
            cin >> c;
            cnt[i][j]=c;
        }
    }
    //
    dp[0][0] = pow(2,n);
    for(long long i = 1;i <= n;++i){
        for(long long j = 0;j <= i; ++j){
            //处理左右边界
            if(j == 0){
                if(cnt[i][j+1]=='*'){
                    dp[i][j]=dp[i-1][j]/2;
                }else{
                    dp[i][j]=0;
                }
            }else if(j == i){
                if(cnt[i][j]=='*'){
                    dp[i][j]=dp[i-1][j-1]/2;
                }else{
                    dp[i][j]=0;
                }
            }else{
                if(cnt[i-1][j]=='.'){
                    dp[i][j]+=dp[i-2][j-1];
                }
                if(cnt[i][j]=='*'){
                    dp[i][j]+=dp[i-1][j-1]/2;
                }
                if(cnt[i][j+1]=='*'){
                    dp[i][j]+=dp[i-1][j]/2;
                }
            }
        }
    }

    long long a = dp[n][m],b = dp[0][0];
    long long gc=gcd(b,a);
    a/=gc;
    b/=gc;
    cout << a<<"/"<<b;

    return 0;
}

4.5算法之动态规划 1413:Mondriaan’s Dream

http://noi.openjudge.cn/ch0405/1413/

题目

描述
Squares and rectangles fascinated the famous Dutch painter Piet Mondriaan. One night, after producing the drawings in his ‘toilet series’ (where he had to use his toilet paper to draw on, for all of his paper was filled with squares and rectangles), he dreamt of filling a large rectangle with small rectangles of width 2 and height 1 in varying ways.

Expert as he was in this material, he saw at a glance that he’ll need a computer to calculate the number of ways to fill the large rectangle whose dimensions were integer values, as well. Help him, so that his dream won’t turn into a nightmare!
输入
The input contains several test cases. Each test case is made up of two integer numbers: the height h and the width w of the large rectangle. Input is terminated by h=w=0. Otherwise, 1<=h,w<=11.
输出
For each test case, output the number of different ways the given rectangle can be filled with small rectangles of size 2 times 1. Assume the given large rectangle is oriented, i.e. count symmetrical tilings multiple times.

思路

基于一下两个思路
0表示下一层对应位置必须为1,即竖向砖块的第一块砖,1表示下一层可为0可为1,无影响
dp思路
dp[i][status] = sum(dp[i-1][k]) k in [0,2^w-1]
其中 sum 求和时要对 status 和 k 进行校验
– status|k == 2^w-1,及保证竖向不会出现连续的两个0这种非法情况
– status&k 要保证所有出现的 1 都为连续的2 个 1,否则意味着出现了单格的错位,010的下层必定为101,则在最低端无法满足全1的要求与操作取到的1为横放的块(1有两种含义),只要保证横放的块都符合规则即可。

源码

//
//  1413.cpp
//  test
//
//  Created by bytedance on 2020/7/29.
//  Copyright © 2020 bytedance. All rights reserved.
//

#include <stdio.h>
#include <vector>
#include <iostream>

using namespace std;
long long w,h;

//bool check(long long x){
//
//}
vector<vector<long long>> dp;
bool check(long long x){
    for(long long i = 0;i < w;++i){
        if((x&(1<<i))!=0){
            if((x&(1<<(i+1)))!=0){
                ++i;
            }else{
                return false;
            }
        }
    }
    return true;
}
int main(){

    while(cin >> h >> w){
        if(h==0&&w==0)break;
        if(h*w%2==1){
            cout<<0<<endl;
            continue;
        }
        long long statusNum = 1<<w;
        dp.clear();
        dp.resize(h+1,vector<long long>(1<<w,0));
        for(long long i = 0;i < statusNum;++i){
            if(check(i))
                dp[1][i]=1;
        }
        for(long long i = 2;i <= h;++i){
            for(long long now = 0;now < statusNum; ++now){
                for(long long up = 0;up < statusNum;++up){
                    if((now|up)==statusNum-1){
                        if(check(now&up))
                            dp[i][now]+=dp[i-1][up];
                    }
                }
            }
        }
        cout << dp[h][statusNum-1]<<endl;
    }
    return 0;
}

4.5算法之动态规划 1249:Humble Numbers 优先级队列

http://noi.openjudge.cn/ch0405/1249/

思路

取出队头,遍历乘四放入队列,即可保证当前队头为最小值

源码

//
//  1249.cpp
//  test
//
//  Created by bytedance on 2020/7/28.
//  Copyright © 2020 bytedance. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;
int m[4]={2,3,5,7};
priority_queue<long long,vector<long long>,greater<long long>> q;
int main(){
    q.push(1);
    int idx = 0;
    int i;
    long long pre = 0;
    while(cin >> i){
        if(i == 0){
            break;
        }

        while(idx<i){
            while(q.top()==pre){
                q.pop();
            }
            pre = q.top();
            idx++;
            for(int i = 0;i < 4;++i){
                q.push(pre*m[i]);
            }
        }
        if(i%100>=10&&i%100<=20)
            printf("The %dth humble number is %lld.\n",i,pre);
        else if(i%10==1)
            printf("The %dst humble number is %lld.\n",i,pre);
        else if(i%10==2)
            printf("The %dnd humble number is %lld.\n",i,pre);
        else if(i%10==3)
            printf("The %drd humble number is %lld.\n",i,pre);
        else
            printf("The %dth humble number is %lld.\n",i,pre);
    }
    return 0;
}

4.3算法之图论 1526:宗教信仰 并查集模板题

http://noi.openjudge.cn/ch0403/1526/

思路

并查集模板题

源码

//
//  1526.cpp
//  test
//
//  Created by bytedance on 2020/7/28.
//  Copyright © 2020 bytedance. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;

vector<int> father;

int find(int x){
    return x==father[x]?x:find(father[x]);
}
void un(int x,int y){
    int fx = find(x);
    int fy = find(y);
    if(fx>fy){
        father[fy]=fx;
    }else{
        father[fx]=fy;
    }
}
int main(){
    int m,n;
    int idx=0;
    while(cin>>n>>m){
        idx++;
        if(n==0&&m==0)break;
        father.clear();
        for(int i = 0;i <=n;++i){
            father.push_back(i);
        }
        while(m--){
            int a,b;
            cin >> a>>b;
            un(a,b);
        }
        int res = 0;
        for(int i = 1;i <=n;++i){
            if(find(i)==i){
                res++;
            }
        }
        cout<<"Case "<< idx<<": "<<res<<endl;
    }
    return 0;
}

4.3算法之图论 1538:Gopher II 匈牙利算法

http://noi.openjudge.cn/ch0403/1538/

思路

二分图最大匹配问题
匈牙利算法模板题

源码

//
//  1538.cpp
//  test
//
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
int n,m,s,v;

struct Node{
    float x,y;
    Node(float x,float y):x(x),y(y){}
};
bool isE(Node &a,Node &b){
    float dis = pow(a.x-b.x,2)+pow(a.y-b.y,2);
    return dis-1.0*s*s*v*v<1e-6;
}


vector<Node> nodesA;
vector<Node> nodesB;
vector<bool> vis;//本次找增广路使
vector<int> to;//记录匹配节点
bool dfs(int x){
    for(int i = 1;i <= m;++i){
        if(!vis[i]&&isE(nodesB[i],nodesA[x])){
            vis[i]=true;
            if(to[i]==0||dfs(to[i])){
                to[i]=x;
                return true;
            }
        }
    }
    return false;
}

int main(){
    while(cin >> n >> m){
        cin >>s>>v;
        to.clear();
        nodesA.clear();
        nodesB.clear();
        vis.resize(m+1,false);
        to.resize(m+1,0);
        nodesA.push_back(Node(-1,-1));
        nodesB.push_back(Node(-1,-1));
        for(int i = 0;i < n;++i){
            float x,y;
            cin >> x>>y;
            nodesA.push_back(Node(x,y));
        }
        for(int i = 0;i < m;++i){
            float x,y;
            cin >> x>>y;
            nodesB.push_back(Node(x,y));
        }
        //dfs二分图匹配
        int res = 0;
        for(int i = 1;i <= n;++i){
            vis.clear();
            vis.resize(m+1,false);
            if(dfs(i)){
                //cout<<"zgl "<<i<<endl;
                res++;
            }
        }
        cout <<n-res<<endl;
    }
    return 0;
}

4.3算法之图论 253:丛林中的路

http://noi.openjudge.cn/ch0403/253

思路

kruskal,边集按照 cost 排序遍历,并查集检查连通性,如果边的两端不连通则加入集合,放进集合

源码
//
//  253.cpp
//  test
//
//  Created by bytedance on 2020/7/26.
//  Copyright © 2020 bytedance. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>

struct Edge{
    int st,ed,cost;
    Edge(int st,int ed,int cost):st(st),ed(ed),cost(cost){}
    bool operator < (const Edge & e) const{
        return cost<e.cost;
    }
};
using namespace std;
int find(vector<int>& father,int x){
    return father[x]==x?x:find(father,father[x]);
}
void un(int x,int y,vector<int> & father){
    int fx = find(father,x);
    int fy = find(father,y);
    if(fx>fy){
        father[fy]=fx;
    }else{
        father[fx]=fy;
    }
}
int main(){
    int num;
    while(cin>>num){
       // cout <<"num"<< num<<endl;
        if(num==0)break;
        vector<int> father(num);
        for(int i = 0;i < num;++i)father[i] = i;
        vector<Edge> edges;
        char stchar;
        num--;
        while(num--){
            cin >> stchar;
            int edgenum;
            cin >> edgenum;
            while(edgenum--){
                char edchar;
                int cost;
                cin >> edchar>>cost;
                edges.push_back(Edge(stchar-'A',edchar-'A',cost));
            }
        }
        sort(edges.begin(),edges.end());
        //kruskal
        int res = 0;
        for(int i = 0;i < edges.size();++i){
            //cout <<"cost"<< edges[i].cost<<endl;
            int st = edges[i].st;
            int ed = edges[i].ed;
            if(find(father,st)!=find(father,ed)){
                res+=edges[i].cost;
                un(st,ed,father);
            }
        }
        cout << res<<endl;

    }
    return 0;
}

4.3算法之图论 726:ROADS

http://noi.openjudge.cn/ch0403/726/

思路

狄杰斯特拉直接改一下,基于优先级队列
Road 设置为二关键字排序
优先级队列 push 时只 push cost 小于等于 k 的 Road,则队列头部 Road.to 为 n 时必为满足 k 的最短路

源码

//
//  726.cpp
//  test
//
//  Created by bytedance on 2020/7/26.
//  Copyright © 2020 bytedance. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <math.h>
#include <queue>
#include <algorithm>
#define INT_MAX 999999999
using namespace std;
int k,n,r;
struct Road{
    int to,d,c;
    Road(int to,int d,int c):to(to),d(d),c(c){}
    bool operator < (const Road &r) const {
        if(d==r.d)return c<r.c;
        return d > r.d;
    }
};
vector<vector<bool>> vis;
vector<int> dis;
vector<vector<Road>> edge;


int main(){
    cin >> k >> n >> r;
    edge.resize(n+1,vector<Road>());
    dis.resize(n+1,INT_MAX);
    vis.resize(n+1,vector<bool>(n+1,false));
    for(int i = 0;i < r;++i){
        int a,b,c,d;
        cin >> a>>b>>c>>d;
        edge[a].push_back(Road(b,c,d));
    }

    priority_queue<Road> q;
    q.push(Road(1,0,0));
    while(!q.empty()){
        Road road = q.top();
        q.pop();
        if(road.to==n){
            cout <<road.d;
            return 0;
        }
        int internal = road.to;
        for(int j = 0;j < edge[internal].size();++j){
            int des = edge[road.to][j].to;
            if(k>=road.c+edge[road.to][j].c){
                q.push(Road(des,road.d+edge[road.to][j].d,road.c+edge[road.to][j].c));
            }
        }
    }

    return 0;
}

4.3算法之图论 799 Heavy Transportation

http://noi.openjudge.cn/ch0403/799/

思路

狄杰斯特拉改一下松弛函数即可
-1代表路径不通

AC源码

//
//  799.cpp
//  test
//
//  Created by bytedance on 2020/7/15.
//  Copyright © 2020 bytedance. All rights reserved.
//

#include <stdio.h>
#include <vector>
#include <iostream>
#include <queue>
#define INT_MAX 999999
#define close -1
using namespace std;

struct Node{
    int d,u;
    Node(int d,int u):d(d),u(u){}
    bool operator <(const Node & a) const{
        return d<a.d;
    }
};
int main(){
    int n;
    cin >> n;
    int vs,es;

    for(int i = 1;i <= n;++i){
        cin >> vs >> es;
        vector<vector<int>> e(vs+1,vector<int>(vs+1,-1));
        vector<bool> vis(vs+1,false);
        vector<int> dis(vs+1,-1);
        while(es--){
            int a,b,c;
            cin >> a>>b>>c;
            e[a][b]=c;
            e[b][a]=c;
        }
        //dijkstra

        priority_queue<Node> q;
        q.push(Node(-1,1));
        dis[1] = INT_MAX;
        while(!q.empty()){
            Node t = q.top();
            q.pop();
            int d = t.d;
            int u = t.u;
            //cout << d<<endl;
            if(vis[u])continue;
            vis[u]=true;
            for(int j = 1;j <= vs; ++j){
                if(!vis[j]&&dis[j]<min(dis[u],e[u][j])){
                    dis[j]=min(dis[u],e[u][j]);
                    q.push(Node(dis[j],j));
                }
            }
        }
        cout <<"Scenario #"<<i<<":"<<endl<<dis[vs]<<endl<<endl;
    }
    return 0;
}