动态规划 – Page 3

HDU 4313 Matrix

July 29, 20152015-07-29hahaschoolLeave a comment

题意

给你一颗树，上面有黑点（母体机器人所在位置），有白点（没有潜伏母体机器人的安全节点），并且给了你每一条边的边权（删边（炸毁道路）需要的时间代价）。现在要你以最小代价删掉一些边，使得没有两个黑点同时可以互相连通。输出这个时间花费即可。

思路

树形DP。这个题和Codeforces 461B Appleman and Tree是一个路子的题，都是在一棵树上不允许同时出现两个联通的特定类别的节点。这种问题我们在思考的时候，方向是将当前的大问题分解成同样的小问题，不断分解到最后，然后考虑怎么样根据一些小问题解得出大问题的解，这是DP的思路所在。

这次，我们设状态表示为 $dp[a][0/1]$ ，其中 $dp[a][0]$ 表示要想让以 $a$ 为根节点的子树满足题目的要求，而且a所在的联通块里面不可以有黑点，需要的最小代价是多少； $dp[a][1]$ 表示要想让以 $a$ 为根节点的子树满足题目要求，且 $a$ 所在的联通块里面有且只有一个黑点，需要的最小代价是多少。

设好了状态，我们开始想DP方程：

我们当前检查的点标号是，我们去逐一检查他的孩子节点，标号是，如果a是一个黑点：
- 因为当前节点是黑点，我们有三种操作可以选：
  - 当前讨论的孩子部分，如果他没有与任何黑点连着，我们可以把这个部分连入当前讨论的根部分，这就是 $dp[b_{i}][0]$ ，即孩子的代价就是根的代价，因为没有切断就没有增加代价。
  - 把根部分和当前讨论的孩子部分中间的边切断，这样的话无论孩子部分到底有没有和黑点连接，都没有关系，只要把孩子的代价加上切断代价就是这样做的代价了，也就是 $dp[b_{i}][0]+cost(a \rightarrow b_{i})$ （孩子部分没有和黑点相连的情况下切断）和 $dp[b_{i}][1]+cost(a \rightarrow b_{i})$ （孩子部分有和黑点相连的情况下切断）。
  - 比较这三种选择，取最优就是局部最优解了。
- $dp[a][0]=\inf$
  黑点不可能不和黑点相连，所以这里用inf屏蔽掉这种选择。
如果a是一个白点：
- 因为当前节点是白色，我们想要让他变成连着黑色的情况，这样的话有四种操作可以选：
  - 假如截止目前和根部连接的所有孩子都不包含黑点，我们可以让现在的这个孩子部分以含有黑点的形态和根部连接，使根部变成有黑点的情况。这就是 $dp[a][0]+dp[b_{i}][1]$ 。
  - 假如当前的根部已经连有黑点，为了满足要求，新联入的部分不可以再包含黑点，这就是 $dp[a][1]+dp[b_{i}][0]$ .
  - 假如孩子部分被切断，这样的话就无所谓孩子长成啥样了，只要算一下代价就可以了，也就是 $dp[b_{i}][0]+cost(a \rightarrow b_{i})$ （孩子部分没有和黑点相连的情况下切断）和 $dp[b_{i}][1]+cost(a \rightarrow b_{i})$ （孩子部分有和黑点相连的情况下切断）。
  - 这四种选择里面选最优的就好了。
- 当前节点是白色，我们想要让她不要根任何黑色连上，这样的话有3种选择：
  - 当前讨论的孩子部分没有和黑色连着，我们可以放心的把这部分连到根部，这就是 $dp[b_{i}][0]$ 。
  - 切断了和孩子部分之间的连接，也就是 $dp[b_{i}][0]+cost(a \rightarrow b_{i})$ （孩子部分没有和黑点相连的情况下切断）和 $dp[b_{i}][1]+cost(a \rightarrow b_{i})$ （孩子部分有和黑点相连的情况下切断）。（其实我已经复制了这一段两遍。。。）
- 注意这两个 $dp[a][0]$ 和 $dp[a][1]$ 要同时处理，因为这里面有一个从“刚才” $dp[a][0]$ 到“现在” $dp[a][1]$ 的转移。

方程想好之后，DFS深入叶子部分，在返回的时候处理好 $dp$ 数组就可以了，最后我们要在 $dp[0][0]$ 和 $dp[0][1]$ 之间取个最小的，因为你所制定的根在最优解的时候连不连黑点并不知道。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;

static long long MAXN = 909303909303;

struct nodeType{
    vector<int> to;
    vector<int> cost;
    int color;
} vertex[100005];

void addEdge(int from,int to,int cost){
    vertex[from].to.push_back(to);
    vertex[from].cost.push_back(cost);
}

long long dp[100005][2];
void dfs(int cur, int par){
    nodeType &currNode = vertex[cur];
    for (int i = 0; i < currNode.to.size(); i++) {
        if (currNode.to[i] != par) {
            dfs(currNode.to[i], cur);
        }
    }
    if (currNode.color == 1) {
        dp[cur][0] = MAXN;
        dp[cur][1] = 0;
        for (int i = 0; i < currNode.to.size(); i++) {
            if (currNode.to[i] != par) {
                dp[cur][1] += min(dp[currNode.to[i]][0],min(dp[currNode.to[i]][0]+currNode.cost[i], dp[currNode.to[i]][1]+currNode.cost[i]));
            }
        }
    }else {
        dp[cur][0] = 0;
        dp[cur][1] = 0;
        for (int i = 0; i < currNode.to.size(); i++) {
            if (currNode.to[i] != par) {
                dp[cur][1] = min(dp[cur][0]+dp[currNode.to[i]][1], min(dp[cur][1]+dp[currNode.to[i]][0],min(dp[cur][1]+dp[currNode.to[i]][0]+currNode.cost[i], dp[cur][1]+dp[currNode.to[i]][1]+currNode.cost[i])));
                dp[cur][0] += min(dp[currNode.to[i]][0], min(dp[currNode.to[i]][0]+currNode.cost[i], dp[currNode.to[i]][1]+currNode.cost[i]));
            }
        }
    }
}

int main(){
    int caseCnt = 0;
    scanf(" %d",&caseCnt);
    while (caseCnt--) {
        int n = 0,k = 0;
        scanf(" %d %d",&n,&k);
        for (int i = 0; i < n; i++) {
            //init
            vertex[i].to.clear();
            vertex[i].cost.clear();
            vertex[i].color = 0;
        }
        for (int i = 0; i < n-1; i++) {
            int a = 0,b = 0,c = 0;
            scanf(" %d %d %d",&a,&b,&c);
            addEdge(a, b, c);
            addEdge(b, a, c);
        }
        for (int i = 0; i < k; i++) {
            int blkpt = 0;
            scanf(" %d",&blkpt);
            vertex[blkpt].color = 1;
        }
        dfs(0, -1);
        cout << min(dp[0][0], dp[0][1]) << endl;
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

static long long MAXN = 909303909303;

struct nodeType{

vector<int> to;

vector<int> cost;

int color;

} vertex[100005];

void addEdge(int from,int to,int cost){

vertex[from].to.push_back(to);

vertex[from].cost.push_back(cost);

}

long long dp[100005][2];

void dfs(int cur, int par){

nodeType &currNode = vertex[cur];

for (int i = 0; i < currNode.to.size(); i++) {

if (currNode.to[i] != par) {

dfs(currNode.to[i], cur);

}

if (currNode.color == 1) {

dp[cur][0] = MAXN;

dp[cur][1] = 0;

for (int i = 0; i < currNode.to.size(); i++) {

if (currNode.to[i] != par) {

dp[cur][1] += min(dp[currNode.to[i]][0],min(dp[currNode.to[i]][0]+currNode.cost[i], dp[currNode.to[i]][1]+currNode.cost[i]));

}

}else {

dp[cur][0] = 0;

dp[cur][1] = 0;

for (int i = 0; i < currNode.to.size(); i++) {

if (currNode.to[i] != par) {

dp[cur][1] = min(dp[cur][0]+dp[currNode.to[i]][1], min(dp[cur][1]+dp[currNode.to[i]][0],min(dp[cur][1]+dp[currNode.to[i]][0]+currNode.cost[i], dp[cur][1]+dp[currNode.to[i]][1]+currNode.cost[i])));

dp[cur][0] += min(dp[currNode.to[i]][0], min(dp[currNode.to[i]][0]+currNode.cost[i], dp[currNode.to[i]][1]+currNode.cost[i]));

}

int main(){

int caseCnt = 0;

scanf(" %d",&caseCnt);

while (caseCnt--) {

int n = 0,k = 0;

scanf(" %d %d",&n,&k);

for (int i = 0; i < n; i++) {

//init

vertex[i].to.clear();

vertex[i].cost.clear();

vertex[i].color = 0;

}

for (int i = 0; i < n-1; i++) {

int a = 0,b = 0,c = 0;

scanf(" %d %d %d",&a,&b,&c);

addEdge(a, b, c);

addEdge(b, a, c);

}

for (int i = 0; i < k; i++) {

int blkpt = 0;

scanf(" %d",&blkpt);

vertex[blkpt].color = 1;

}

dfs(0, -1);

cout << min(dp[0][0], dp[0][1]) << endl;

}

return 0;

}

Codeforces 461B Appleman and Tree

July 29, 20152015-07-29hahaschoolLeave a comment

题意

给你一颗树，上面有黑色节点，也有白色节点，现在你要做的事情是，在这棵树上选出几条边，去掉，这样的话这棵树就会变成好多小树，这些小树一定要含且只含一个黑色点。问你有多少种不同的方法删边来满足要求。

思路

树形DP。往DP方面去想是因为原始的大问题可以进行剖分，即如果我们想要知道将整棵树按要求切割的方案个数，我们可以去考虑它的子树按要求切割的方案个数，对于子树也是同样地进行剖分。确定了将问题剖分的方向之后，就是确定状态了。

我们发现，要想从一颗树的子树的分割情况得到整棵树的分割情况，我们不仅要知道子树符合要求的分割情况，也要知道子树不符合要求的分割情况，这样才能覆盖全部情况。因此我们设定状态为 $dp[a][0/1]$ ，其中 $dp[a][0]$ 存值为将以 $a$ 为根节点的子树进行分割，而且与当前的子树根节点相连的节点中没有黑色节点方法个数； $dp[a][1]$ 存值为将以 $a$ 为根节点的子树进行分割，而且与当前的子树根节点相连的节点中有且仅有一个黑色节点方法个数。

这里一定要清楚，0/1表示的是与根节点联通的节点中是不是有黑色的节点，已经断开的地方，我们不用关心。

接下来讨论状态的转移：

如果当前节点已经是叶子节点，节点编号是：
- 如果是黑色节点：
  - $dp[a][0] = 0$ 因为黑色节点为根部的子树不可能不含有黑色节点。
  - $dp[a][1] = 1$ 因为只有黑色节点一个点，只有一种分割方式就是把节点自己当作一颗树。
- 如果是白色节点：
  - $dp[a][0] = 1$ 因为白色叶子节点的子树中只有他自己一个白色节点，不可能含有黑色节点了，分割方式也只有一种就是把自己当成子树。
  - $dp[a][1] = 0$ 因为白色叶子节点的子树中不可能含有黑色节点。
如果当前节点不是叶子节点，节点编号是，它的孩子节点们的编号为b_{i}：
- 如果是白色节点：
  - ，我们逐一检查每一个孩子节点，我们想得到的结果是当前节点直接相连的联通块里面不存在黑色节点，那么：
    - 如果当前检查的孩子节点是黑色的，我们考虑切开还是不切开同这个孩子节点连接的边：
      - 不切开的话，要求连接的孩子部分一定不可以有黑色节点，这显然是不可能的，不过黑色节点的 $dp[a][0] = 0$ 始终是0，所以没关系。
      - 切开的话，就要求切开之后的孩子部分自己可以满足要求，这样的话有 $dp[b_{i}][1]$ 种方法。
    - 如果当前检查的孩子节点是白色的，我们考虑切开／不切开同孩子连接的边：
      - 切开的话，孩子部分自己要满足要求，这样的话有 $dp[b_{i}][1]$ 种方法。
      - 不切开的话，孩子部分与根节点直接相连的部分一定不可以包含黑色节点，这样的话有 $dp[b_{i}][0]$ 种方法。
  - ，这个方程的计算必须和上面的同步进行。这个有一点不好懂，其实可以这么想：
    - $dp[a][1]*(dp[b_{i}][0]+dp[b_{i}][1])$ 这一部分，我们要想的过程是将一个已经连接好了黑点的根部，讨论是不是要和当前的孩子相连的过程：
    - 如果当前检查的节点是黑色节点，我们还是考虑切开／不切开：
      - 不切开的话不满足要求，不过黑色节点的 $dp[a][0] = 0$ 始终是0，所以没关系。
      - 切开的话，连接上去的孩子部分一定要满足要求，有且只有一个黑点，所以有 $dp[b_{i}][1]$ 种方法。
    - 如果当前检查的是白色节点，切开／不切开：
      - 不切开的话，还是不满足要求，但是如果这个时候在根节点上已经有带黑点的联通块连上去了，这个时候只要令连接上去的部分没有黑点就可以了，所以有 $dp[b_{i}][0]$ 种方法。
      - 切开的话，孩子部分要自己保持成立，有且只有一个黑点，所以有 $dp[b_{i}][1]$ 种方法。
    - 而 $dp[a][0]*dp[b_{i}][1]$ 这一部分，想法是当前依然不成立的根部，和带有一个黑点的孩子部分连接。
- 如果是黑色节点：
  - $dp[a][0] = 0$ 因为黑色节点为根部的子树不可能不含有黑色节点
  - 我们逐一检查每一个孩子节点，既然我们想得到的结果是当前节点直接相连的联通块里面只有一个黑色节点，那么：
    - 如果当前检查的孩子节点是黑色的，我们考虑切开还是不切开同这个孩子节点连接的边：
      - 切开的话，没有问题，因为当前考虑的子树的根节点已经是黑的了，而且还要让让切开之后切出来的孩子的那一部分保持成立，要想做到这一点的话有 $dp[b_{i}][1]$ 种方法。
      - 不切开的话，显然是不行的，因为这样就有了两个黑色节点，不过黑色节点的 $dp[a][0] = 0$ 始终是0，所以加进去也没关系。
    - 如果当前检查的孩子节点是白色的，我们考虑切开／不切开同孩子连接的边：
      - 切开的话，还要保证切除的孩子部分也成立，因此孩子部分有 $dp[b_{i}][1]$ 种方法。
      - 不切开的话，因为当前节点是黑色的，链接孩子节点之后，连接上的部分不可以含有黑色节点，孩子节点能做到这样的方法有 $dp[b_{i}][0]$ 种。

写了一堆废话其实就是为了理清思路，思维能力太弱只能这样了。DP的思路搞定之后，具体的操作就非常简单，利用DFS深入叶子，在返回的过程中进行对孩子的考察和对自身的更新，最后在根节点上读取答案。

代码

//
//  CF461B.cpp
//  playground
//
//  Created by Adam Chang on 2015/07/29.
//  Copyright © 2015年 Adam Chang. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;

static long long MODER = 1000000007;

struct nodeType{
    vector<int> to;
    int color;
} vertex[100005];

void addEdge(int from,int to){
    vertex[from].to.push_back(to);
}

long long dp[100005][2];
void dfs(int cur,int par){
    nodeType &currNode = vertex[cur];
    for (int i = 0; i < currNode.to.size(); i++) {
        if (currNode.to[i] != par) {
            dfs(currNode.to[i],cur);
        }
    }
    if (currNode.color == 1) {
        dp[cur][0] = 0;
        dp[cur][1] = 1;
        for (int i = 0; i < currNode.to.size(); i++) {
            if (currNode.to[i] != par) {
                dp[cur][1] *= dp[currNode.to[i]][0] + dp[currNode.to[i]][1];
                dp[cur][1] %= MODER;
            }
        }
    }else {
        dp[cur][0] = 1;
        dp[cur][1] = 0;
        for (int i = 0; i < currNode.to.size(); i++) {
            if (currNode.to[i] != par) {
                dp[cur][1] = dp[cur][0] * dp[currNode.to[i]][1] + dp[cur][1] * (dp[currNode.to[i]][0] + dp[currNode.to[i]][1]);
                dp[cur][1] %= MODER;
                dp[cur][0] *= dp[currNode.to[i]][0] + dp[currNode.to[i]][1];
                dp[cur][0] %= MODER;
            }
        }
    }
}

int main(){
    int n = 0;
    scanf(" %d",&n);
    for (int i = 0; i < n; i++) {
        vertex[i].to.clear();
    }
    for (int i = 1; i < n; i++) {
        int to;
        scanf(" %d",&to);
        addEdge(i, to);
        addEdge(to, i);
    }
    for (int i = 0; i < n; i++) {
        scanf(" %d",&vertex[i].color);
    }
    dfs(0,-1);
    cout << (dp[0][1] + MODER) % MODER << endl;
    return 0;
}

// CF461B.cpp

// playground

// Created by Adam Chang on 2015/07/29.

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

static long long MODER = 1000000007;

struct nodeType{

vector<int> to;

int color;

} vertex[100005];

void addEdge(int from,int to){

vertex[from].to.push_back(to);

}

long long dp[100005][2];

void dfs(int cur,int par){

nodeType &currNode = vertex[cur];

for (int i = 0; i < currNode.to.size(); i++) {

if (currNode.to[i] != par) {

dfs(currNode.to[i],cur);

}

if (currNode.color == 1) {

dp[cur][0] = 0;

dp[cur][1] = 1;

for (int i = 0; i < currNode.to.size(); i++) {

if (currNode.to[i] != par) {

dp[cur][1] *= dp[currNode.to[i]][0] + dp[currNode.to[i]][1];

dp[cur][1] %= MODER;

}

}else {

dp[cur][0] = 1;

dp[cur][1] = 0;

for (int i = 0; i < currNode.to.size(); i++) {

if (currNode.to[i] != par) {

dp[cur][1] = dp[cur][0] * dp[currNode.to[i]][1] + dp[cur][1] * (dp[currNode.to[i]][0] + dp[currNode.to[i]][1]);

dp[cur][1] %= MODER;

dp[cur][0] *= dp[currNode.to[i]][0] + dp[currNode.to[i]][1];

dp[cur][0] %= MODER;

}

int main(){

int n = 0;

scanf(" %d",&n);

for (int i = 0; i < n; i++) {

vertex[i].to.clear();

}

for (int i = 1; i < n; i++) {

int to;

scanf(" %d",&to);

addEdge(i, to);

addEdge(to, i);

}

for (int i = 0; i < n; i++) {

scanf(" %d",&vertex[i].color);

}

dfs(0,-1);

cout << (dp[0][1] + MODER) % MODER << endl;

return 0;

}

POJ 3744 Scout YYF I

April 08, 20152015-04-08hahaschoolOne Comment

题意

某人在直线上走，直线上有若干格子，起点是1号格，每次这个人都有p概率走1格，1-p概率走二格，有一些格子有地雷，走上去就被爆了，所以要你求你能安全走到终点（可以看成是站在n+1号格）上概率。

思路

每一个格子的概率都可以通过它前两个的格子的概率推出来，这样的话跟斐波那契很像。
联想我们想快速地搞出来一个非常大的fib值的方法是什么？快速幂。
所以这个题我们用快速幂来做。

dp方程其实都不叫dp，叫递推，大概长这个样子：

$\begin{bmatrix}p&1-p\\1&0 \end{bmatrix}\begin{bmatrix}p_{n} \\ p_{n-1}\end{bmatrix}=\begin{bmatrix} p_{n+1}\\p_{n}\end{bmatrix}$

直接矩阵乘法模版＋快速幂就行。

处理地雷的话，你就先走到地雷那里，停一下，把地雷格的dp值抹成0，然后继续往下走，走到下一个地雷，最后走到终点。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>

using namespace std;

const int N = 2;
int n;

struct Mat {
    double mat[N][N];
};
Mat operator * (Mat a, Mat b) {
    Mat c;
    memset(c.mat, 0, sizeof(c.mat));
    int i, j, k;
    for(k = 0; k < N; ++k) {
        for(i = 0; i < N; ++i) {
            for(j = 0; j < N; ++j) {
                c.mat[i][j] += a.mat[i][k] * b.mat[k][j];
            }
        }
    }
    return c;
}
Mat operator ^ (Mat a, int k) {
    Mat c;
    int i, j;
    for(i = 0; i < N; ++i)
        for(j = 0; j < N; ++j)
            c.mat[i][j] = (i == j);    //初始化为单位矩阵

    for(; k; k >>= 1) {
        if(k&1) c = c*a;

        a = a*a;
    }
    return c;
}


int main(){
    while(cin >> n){
        double p = 0;
        cin >> p;
        vector<double> mine;
        mine.push_back(0);
        for(int i = 1;i <= n;i++){
            int tmp = 0;
            cin >> tmp;
            mine.push_back(tmp);
        }
        sort(mine.begin(),mine.end());
        Mat a,b;
        double dn = 1;
        for(int i = 1;i < mine.size();i++){
            a.mat[0][0] = p;
            a.mat[0][1] = 1-p;
            a.mat[1][0] = 1;
            a.mat[1][1] = 0;
            Mat c = a^(mine[i]-mine[i-1]);
            b.mat[0][0] = 0;
            b.mat[0][1] = 0;
            b.mat[1][0] = dn;
            b.mat[1][1] = 0;
            Mat d = c * b;
            dn = d.mat[1][0];
        }
        printf("%.7f\n",dn);
    }


    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

using namespace std;

const int N = 2;

int n;

struct Mat {

double mat[N][N];

};

Mat operator * (Mat a, Mat b) {

Mat c;

memset(c.mat, 0, sizeof(c.mat));

int i, j, k;

for(k = 0; k < N; ++k) {

for(i = 0; i < N; ++i) {

for(j = 0; j < N; ++j) {

c.mat[i][j] += a.mat[i][k] * b.mat[k][j];

}

return c;

}

Mat operator ^ (Mat a, int k) {

Mat c;

int i, j;

for(i = 0; i < N; ++i)

for(j = 0; j < N; ++j)

c.mat[i][j] = (i == j); //初始化为单位矩阵

for(; k; k >>= 1) {

if(k&1) c = c*a;

a = a*a;

}

return c;

}

int main(){

while(cin >> n){

double p = 0;

cin >> p;

vector<double> mine;

mine.push_back(0);

for(int i = 1;i <= n;i++){

int tmp = 0;

cin >> tmp;

mine.push_back(tmp);

}

sort(mine.begin(),mine.end());

Mat a,b;

double dn = 1;

for(int i = 1;i < mine.size();i++){

a.mat[0][0] = p;

a.mat[0][1] = 1-p;

a.mat[1][0] = 1;

a.mat[1][1] = 0;

Mat c = a^(mine[i]-mine[i-1]);

b.mat[0][0] = 0;

b.mat[0][1] = 0;

b.mat[1][0] = dn;

b.mat[1][1] = 0;

Mat d = c * b;

dn = d.mat[1][0];

}

printf("%.7f\n",dn);

}

return 0;

}

HDU 4405 Aeroplane chess

April 08, 20152015-04-08hahaschoolLeave a comment

题意

玩线性飞行棋，一共有n个格子，每一次扔骰子，扔几点走几格，如果踩到了跳跃格，就跳过去，而且可以连续跳跃，走到或冲过终点游戏就胜利。问你扔多少次骰子之后游戏胜利（求期望）。

思路

很直接的概率dp题，加上了跳跃，不过因为我们的方向始终如一，所以没有成环的悲剧发生，可以很轻松的解出来。
我们设dp[i]表示位于第i格时，完成游戏需要的扔骰子数目,那么我们有：

$dp[i]=\sum_{k=1}^{6}(\frac{1}{6}dp[i+k])+1$

对于a to b的跳跃关系，我们又有：

$dp[a]=dp[b]$

这样dp方程就推好了。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>

using namespace std;

int fly[100010];
double dp[100010];

int flyme(int i){
    if (fly[i]) {
        return fly[i] = flyme(fly[i]);
    }else{
        return i;
    }

}

int main(){
    int n = 0,m = 0;
    while (scanf(" %d %d",&n,&m)) {
        if (!(n+m)) {
            break;
        }
        memset(dp, 0, sizeof(dp));
        memset(fly, 0, sizeof(fly));
        for (int i = 1; i <= m; i++) {
            int from = 0,to = 0;
            scanf(" %d %d",&from,&to);
            fly[from] = to;
        }
        for (int i = n-1; i >= 0;i--) {
            for (int j = 1; j <= 6; j++) {
                dp[i] += dp[flyme(i+j)]/6;
            }
            dp[i]++;
        }
        printf("%.4lf\n",dp[0]);
    }

    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

using namespace std;

int fly[100010];

double dp[100010];

int flyme(int i){

if (fly[i]) {

return fly[i] = flyme(fly[i]);

}else{

return i;

}

int main(){

int n = 0,m = 0;

while (scanf(" %d %d",&n,&m)) {

if (!(n+m)) {

break;

}

memset(dp, 0, sizeof(dp));

memset(fly, 0, sizeof(fly));

for (int i = 1; i <= m; i++) {

int from = 0,to = 0;

scanf(" %d %d",&from,&to);

fly[from] = to;

}

for (int i = n-1; i >= 0;i--) {

for (int j = 1; j <= 6; j++) {

dp[i] += dp[flyme(i+j)]/6;

}

dp[i]++;

}

printf("%.4lf\n",dp[0]);

}

return 0;

}

POJ 2096 Collecting Bugs

April 07, 20152015-04-07hahaschoolLeave a comment

题意

给软件挑bug，每天挑出来一个，每个bug都有两个属性：分类和子系统，这两个属性都是完全随机的，已知一共有n个分类，s个子系统，问你挑出的bug完全覆盖全部分类和子系统需要多长时间（求期望）。

思路

优惠券问题的变种，相当于升高到了二维，因此dp数组也要开成二维。

我们设定dp[i][j]表示距离完成任务还有i个分类j个子系统没有覆盖，状态的转移用如下几种：
1.挑出的bug属于全新的分类和子系统
2.挑出的bug仅仅属于全新的分类
3.挑出的bug仅仅属于全新的子系统
4.挑出的bug没有任何新意
这样，我们可以得出状态转移方程： $dp[i][j]=\frac{i}{n}\frac{j}{s}dp[i-1][j-1]+\frac{n-i}{n}\frac{j}{s}dp[i][j-1]+\frac{i}{n}\frac{n-j}{s}dp[i-1][j]+\frac{n-i}{n}\frac{n-j}{s}dp[i][j]+1$

经过化简可以发现这是个很直接的递推方程了，所以可以很轻松的出答案了。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>

using namespace std;

double dp[1010][1010];

int main(){
    int in = 0,im = 0;
    while (cin >> in >> im) {
        double n = in,m = im;
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 0;
        for (int ii = 1; ii <= in; ii++) {
            double i = ii;
            dp[ii][0] = dp[ii-1][0] + n/i;
        }
        for (int ii = 1; ii <= im; ii++) {
            double i = ii;
            dp[0][ii] = dp[0][ii-1] + m/i;
        }
        for (int ii = 1; ii <= in; ii++) {
            for (int ij = 1; ij <= im; ij++) {
                double i = ii,j = ij;
                dp[ii][ij] = (i*j)*dp[ii-1][ij-1]+(n-i)*j*dp[ii][ij-1]+i*(m-j)*dp[ii-1][ij]+m*n;
                dp[ii][ij] /= m*n-(n-i)*(m-j);
            }
        }
        printf("%.4lf\n",dp[in][im]);
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

using namespace std;

double dp[1010][1010];

int main(){

int in = 0,im = 0;

while (cin >> in >> im) {

double n = in,m = im;

memset(dp, 0, sizeof(dp));

dp[0][0] = 0;

for (int ii = 1; ii <= in; ii++) {

double i = ii;

dp[ii][0] = dp[ii-1][0] + n/i;

}

for (int ii = 1; ii <= im; ii++) {

double i = ii;

dp[0][ii] = dp[0][ii-1] + m/i;

}

for (int ii = 1; ii <= in; ii++) {

for (int ij = 1; ij <= im; ij++) {

double i = ii,j = ij;

dp[ii][ij] = (i*j)*dp[ii-1][ij-1]+(n-i)*j*dp[ii][ij-1]+i*(m-j)*dp[ii-1][ij]+m*n;

dp[ii][ij] /= m*n-(n-i)*(m-j);

}

printf("%.4lf\n",dp[in][im]);

}

return 0;

}

HDU 4035 Maze

April 06, 20152015-04-06hahaschoolLeave a comment

题意

一个人被丢进了迷宫，迷宫有n个房间，1号房间作为起点，房间之间以隧道联通，任意两个房间的通路只有一条，每进入一个房间，有k的概率被干掉，然后在1号房间复活，有e的概率直接脱出迷宫，若上述两事件未发生，则这个人会从当前房间的全部隧道中随便选一个进去（即使沿着刚才的路返回）。问你这个人要穿过多少隧道才能拖出迷宫（求期望）。

思路

注意审题，“任意两个房间的通路只有一条” ，这句话告诉我们迷宫可以抽象为一棵树（因为没有环，起点确定所以看作树根），又因为是求期望，所以这是一个树上进行的概率dp。
对于每个节点，我们定义dp数组为dp[i]表示在i号房间脱出迷宫的期望穿洞数。
接下来就是处理dp方程，如果你可以写出来dp方程的话，你会发现这个方程有两种版本，一种是叶子节点，一种是普通节点（其实还有一种根节点，不过这个只是最后出答案用的），列完之后我们会发现dp方程组成环，而且每一个方程式都有着类似的未知项（或者说是格式统一），面对这种情况就可以归纳出方程的一般形式，建立几个系数数组，回代一般形式，确定出系数数组的递推关系式，化环为链。这种情形经常出现在概率dp问题中。
最后需要注意本题有坑点：判断误解的时候，需要直接判断1-A[1](这个是什么请看下面的数学推导）的绝对值是否非常小（分母趋向于0），在这里卡精度，你至少需要1e-9的精度。在这里用其他的方法判断一律是过不了的～

代码

//
//  HDU4035.cpp
//  playground
//
//  Created by Adam Chang on 2015/4/5.
//  Copyright (c) 2015年 Adam Chang. All rights reserved.
//
//Review: Each pair of rooms is connected by one and only one path
//this statement marks the structure is tree (or DAG),i.e. no rings.

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>

using namespace std;

struct vertexType{
    vector<int> to;
    double pk,pe;
    void init(){
        to.clear();
        pk = 0;
        pe = 0;
    }
} vertex[10005];

double A[10005],B[10005],C[10005];
bool vis[10005];
void dfs(int father){
    vis[father] = true;
    vector<int> child;
    for (int i = 0; i < vertex[father].to.size(); i++) {
        int next = vertex[father].to[i];
        if (vis[next]) {
            continue;
        }
        child.push_back(next);
        dfs(next);
    }

    double w = 1-vertex[father].pk-vertex[father].pe;
    if (child.size()) {
        //normal vertex
        double m = (double)vertex[father].to.size();
        double q = 1;
        double e = vertex[father].pk;
        double r = w;
        for (int i = 0; i < child.size(); i++) {
            e += w/m*A[child[i]];
            q -= w/m*B[child[i]];
            r += w/m*C[child[i]];
        }
        A[father] = e/q;
        B[father] = w/m/q;
        C[father] = r/q;
    }else{
        //endpoint vertex
        A[father] = vertex[father].pk;
        B[father] = w;
        C[father] = w;
    }
}


int main(){
    int caseCnt;
    scanf(" %d",&caseCnt);
    for (int ci = 1; ci <= caseCnt; ci++) {
        int n = 0;
        scanf(" %d",&n);
        for (int i = 1; i <= n; i++) {
            vertex[i].init();
        }
        for (int i = 1; i <= n-1; i++) {
            int arg1,arg2;
            scanf(" %d %d",&arg1,&arg2);
            vertex[arg1].to.push_back(arg2);
            vertex[arg2].to.push_back(arg1);
        }
        for (int i = 1; i <= n; i++) {
            double arg1,arg2;
            scanf(" %lf %lf",&arg1,&arg2);
            vertex[i].pk = arg1/100;
            vertex[i].pe = arg2/100;
        }
        memset(A, 0, sizeof(A));
        memset(B, 0, sizeof(B));
        memset(C, 0, sizeof(C));
        memset(vis, 0, sizeof(vis));
        dfs(1);
        if (abs(1-A[1]) < 0.000000001) {//这里卡精度
            printf("Case %d: impossible\n",ci);
            continue;
        }
        printf("Case %d: %.10lf\n",ci,C[1]/(1-A[1]));
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

// HDU4035.cpp

// playground

// Created by Adam Chang on 2015/4/5.

//Review: Each pair of rooms is connected by one and only one path

//this statement marks the structure is tree (or DAG),i.e. no rings.

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

using namespace std;

struct vertexType{

vector<int> to;

double pk,pe;

void init(){

to.clear();

pk = 0;

pe = 0;

}

} vertex[10005];

double A[10005],B[10005],C[10005];

bool vis[10005];

void dfs(int father){

vis[father] = true;

vector<int> child;

for (int i = 0; i < vertex[father].to.size(); i++) {

int next = vertex[father].to[i];

if (vis[next]) {

continue;

}

child.push_back(next);

dfs(next);

}

double w = 1-vertex[father].pk-vertex[father].pe;

if (child.size()) {

//normal vertex

double m = (double)vertex[father].to.size();

double q = 1;

double e = vertex[father].pk;

double r = w;

for (int i = 0; i < child.size(); i++) {

e += w/m*A[child[i]];

q -= w/m*B[child[i]];

r += w/m*C[child[i]];

}

A[father] = e/q;

B[father] = w/m/q;

C[father] = r/q;

}else{

//endpoint vertex

A[father] = vertex[father].pk;

B[father] = w;

C[father] = w;

}

int main(){

int caseCnt;

scanf(" %d",&caseCnt);

for (int ci = 1; ci <= caseCnt; ci++) {

int n = 0;

scanf(" %d",&n);

for (int i = 1; i <= n; i++) {

vertex[i].init();

}

for (int i = 1; i <= n-1; i++) {

int arg1,arg2;

scanf(" %d %d",&arg1,&arg2);

vertex[arg1].to.push_back(arg2);

vertex[arg2].to.push_back(arg1);

}

for (int i = 1; i <= n; i++) {

double arg1,arg2;

scanf(" %lf %lf",&arg1,&arg2);

vertex[i].pk = arg1/100;

vertex[i].pe = arg2/100;

}

memset(A, 0, sizeof(A));

memset(B, 0, sizeof(B));

memset(C, 0, sizeof(C));

memset(vis, 0, sizeof(vis));

dfs(1);

if (abs(1-A[1]) < 0.000000001) {//这里卡精度

printf("Case %d: impossible\n",ci);

continue;

}

printf("Case %d: %.10lf\n",ci,C[1]/(1-A[1]));

}

return 0;

}

SGU 104 Little shop of flowers

April 01, 20152015-04-01hahaschoolLeave a comment

题意

插花，给你若干花瓶和若干把花，花瓶个数大于等于花的把数，每把花都不一样，要求你让每把花都插进花瓶里面，花瓶不一定每个都要用，但是你必须保证插完之后花的排列顺序和原来给出的一样。然后给了你一个花插进花瓶之后产生的美学价值对照表，要你设计一种方案使得这样插花所达到的美学价值最大。

思路

典型的背包问题，我们设计一个二维dp数组dp[i][j]，令i表示当前已经考虑到第几把花，令j表示对于当前这把花我们插入到前j个花瓶，那么我们一把一把花处理，对于每把花枚举其插入每个花瓶的结果，同时要继承上一把花插入到这个花瓶之前的全部状态中最优的那个（因为要保证有序）。最后枚举dp[n][j]的j，找到最佳状态就好了。
接下来要考虑怎么输出最优方案，其实不难想，我们可以给dp数组加上一维或者单开一个pre[i][j]数组，与dp数组平行工作，保存当前状态的前置状态，最后顺着最佳状态不断回溯输出就搞定了。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>

using namespace std;

int aes[105][105];
int dp[105][105][2]; // 0 is value 1 is pre

int main(){
    int f = 0,v = 0;
    scanf(" %d %d",&f,&v);
    memset(aes, 0, sizeof(aes));
    for (int i = 1; i <= f; i++) {
        for (int j = 1; j <= v; j++) {
            scanf(" %d",&aes[i][j]);
        }
    }
    memset(dp, 0xf3f3, sizeof(dp));
    for (int i = 1; i <= v; i++) {
        dp[1][i][0] = aes[1][i];
        dp[1][i][1] = 0;
    }
    for (int i = 1; i <= f; i++) {
        for (int j = 2; j <= v; j++) {
            for (int k = 1;k < j; k++) {
                if (dp[i][j][0] < dp[i-1][k][0] + aes[i][j]) {
                    dp[i][j][0] = dp[i-1][k][0] + aes[i][j];
                    dp[i][j][1] = k;
                }
            }
        }
    }
    int maxn = 0xf3f3f3f3,maxi = 0;
    for (int i = 1; i <= v; i++) {
        if (dp[f][i][0] > maxn) {
            maxn = dp[f][i][0];
            maxi = i;
        }
    }
    stack<int> curstk;
    int cur = maxi;
    while (f) {
        curstk.push(cur);
        cur = dp[f--][cur][1];
    }
    printf("%dn",maxn);
    while (curstk.size() > 1) {
        printf("%d ",curstk.top());
        curstk.pop();
    }
    printf("%dn",curstk.top());
    curstk.pop();

    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

using namespace std;

int aes[105][105];

int dp[105][105][2]; // 0 is value 1 is pre

int main(){

int f = 0,v = 0;

scanf(" %d %d",&f,&v);

memset(aes, 0, sizeof(aes));

for (int i = 1; i <= f; i++) {

for (int j = 1; j <= v; j++) {

scanf(" %d",&aes[i][j]);

}

memset(dp, 0xf3f3, sizeof(dp));

for (int i = 1; i <= v; i++) {

dp[1][i][0] = aes[1][i];

dp[1][i][1] = 0;

}

for (int i = 1; i <= f; i++) {

for (int j = 2; j <= v; j++) {

for (int k = 1;k < j; k++) {

if (dp[i][j][0] < dp[i-1][k][0] + aes[i][j]) {

dp[i][j][0] = dp[i-1][k][0] + aes[i][j];

dp[i][j][1] = k;

}

int maxn = 0xf3f3f3f3,maxi = 0;

for (int i = 1; i <= v; i++) {

if (dp[f][i][0] > maxn) {

maxn = dp[f][i][0];

maxi = i;

}

stack<int> curstk;

int cur = maxi;

while (f) {

curstk.push(cur);

cur = dp[f--][cur][1];

}

printf("%dn",maxn);

while (curstk.size() > 1) {

printf("%d ",curstk.top());

curstk.pop();

}

printf("%dn",curstk.top());

curstk.pop();

return 0;

}

Codeforces 118D Caesar's Legions

March 22, 20152015-03-22hahaschoolLeave a comment

题意

给你两种士兵，n1个A和n2个B，同种士兵是一样的，不分先后，然后你最多能把k1个A排到一起k2个B排到一起，问你有多少种有效排法。

思路

动态规划，建一个三维dp数组，其实是一个二维的表，每个格子有两个值，dp[i][j]表示截至目前只使用i个A，j个B来进行排列，dp[i][j][0]表示以A结尾的排列序列个数,dp[i][j][1]表示以B结尾的排列序列个数，之后我们来转移状态，对于当前的以A结尾的排列，我们可以再其末尾加1～k2个B，构成新的以B结尾的排列，所以我们就可以把dp[i][j+k][1]更新了（k表示加几个B）。同样的，用B结尾排列个数的值更新之后的A结尾排列个数的值，把这个表这样逐步打好，最后输出dp[n1][n2][0]+dp[n1][n2][1]即可。

接下来上代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>

using namespace std;

int dp[120][120][2];

#define MODER 100000000

int main(){
    int n1 = 0,n2 = 0,k1 = 0,k2 = 0;
    memset(dp, 0, sizeof(dp));
    cin >> n1 >> n2 >> k1 >> k2;
    for (int i = 1; i <= k1; i++) {
        dp[i][0][0] = 1;
    }
    for (int j = 1; j <= k2; j++) {
        dp[0][j][1] = 1;
    }
    for (int i = 0; i <= 100; i++) {
        for (int j = 0; j <= 100; j++) {
            for (int k = 1; k <= k2; k++) {
                dp[i][j+k][1] += dp[i][j][0] % MODER;
                dp[i][j+k][1] %= MODER;
            }
        }
        for (int j = 1; j <= 100; j++) {
            for (int k = 1; k <= k1; k++) {
                dp[i+k][j][0] += dp[i][j][1] % MODER;
                dp[i+k][j][0] %= MODER;
            }
        }
    }
    cout << (dp[n1][n2][0]+dp[n1][n2][1]+MODER)%MODER << endl;

    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

using namespace std;

int dp[120][120][2];

#define MODER 100000000

int main(){

int n1 = 0,n2 = 0,k1 = 0,k2 = 0;

memset(dp, 0, sizeof(dp));

cin >> n1 >> n2 >> k1 >> k2;

for (int i = 1; i <= k1; i++) {

dp[i][0][0] = 1;

}

for (int j = 1; j <= k2; j++) {

dp[0][j][1] = 1;

}

for (int i = 0; i <= 100; i++) {

for (int j = 0; j <= 100; j++) {

for (int k = 1; k <= k2; k++) {

dp[i][j+k][1] += dp[i][j][0] % MODER;

dp[i][j+k][1] %= MODER;

}

for (int j = 1; j <= 100; j++) {

for (int k = 1; k <= k1; k++) {

dp[i+k][j][0] += dp[i][j][1] % MODER;

dp[i+k][j][0] %= MODER;

}

cout << (dp[n1][n2][0]+dp[n1][n2][1]+MODER)%MODER << endl;

return 0;

}

HDU 3466 Proud Merchants

January 26, 20152015-01-26hahaschoolLeave a comment

#include <iostream>
#include <sstream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <map>
#include <list>
#include <stack>

using namespace std;

struct itemType{
    int p,q,v;
};

int dp[505][5005];//before puchase
itemType item[505];

bool cmp(itemType a,itemType b){
    return a.q-a.p > b.q-b.p;
}

int main(){
    int n = 0,m = 0;
    while(cin >> n >> m){
        memset(dp, 0, sizeof(dp));
        memset(item, 0, sizeof(item));

        int res = 0;
        for (int i = 1; i <= n;i++) {
            cin >> item[i].p >> item[i].q >> item[i].v;
        }

         sort(item+1, item+1+n, cmp);
        for (int i = 1; i <= n; i++) {
            for(int j = m;j >= 0;j--) {
                if (j < item[i].q) {
                    //cannot buy
                    dp[i][j] = max(dp[i-1][j],dp[i][j]);
                }else{
                    //can buy
                    dp[i][j] = max(dp[i-1][j],dp[i][j]);
                    dp[i][j-item[i].p] = max(dp[i-1][j]+item[i].v,dp[i-1][j]);
                }
                res = max(res,dp[i][j]);
            }
        }


        cout << res << endl;
    }

    return 0;
}

#include <iostream>

#include <sstream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <map>

#include <list>

#include <stack>

using namespace std;

struct itemType{

int p,q,v;

};

int dp[505][5005];//before puchase

itemType item[505];

bool cmp(itemType a,itemType b){

return a.q-a.p > b.q-b.p;

}

int main(){

int n = 0,m = 0;

while(cin >> n >> m){

memset(dp, 0, sizeof(dp));

memset(item, 0, sizeof(item));

int res = 0;

for (int i = 1; i <= n;i++) {

cin >> item[i].p >> item[i].q >> item[i].v;

}

sort(item+1, item+1+n, cmp);

for (int i = 1; i <= n; i++) {

for(int j = m;j >= 0;j--) {

if (j < item[i].q) {

//cannot buy

dp[i][j] = max(dp[i-1][j],dp[i][j]);

}else{

//can buy

dp[i][j] = max(dp[i-1][j],dp[i][j]);

dp[i][j-item[i].p] = max(dp[i-1][j]+item[i].v,dp[i-1][j]);

}

res = max(res,dp[i][j]);

}

cout << res << endl;

}

return 0;

}

这是个需要排序预处理的01背包问题（够sxbk），排序的基准是q-p小的在前。

至于为啥。。。我是可耻的翻了题解才知道怎么做的，这位讲的清楚明白：

http://blog.csdn.net/oceanlight/article/details/7866759

HDU 1028 Ignatius and the Princess III 拆分数问题(顺序无关型)

January 26, 20152015-01-26hahaschoolLeave a comment

//Problem F
/*
#include <iostream>
#include <sstream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <map>
#include <list>
#include <stack>

using namespace std;

long long dp[125][125];

void solve(){
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= 120; i++) {
        dp[i][0] = 1;
        dp[1][i] = 1;
    }
    for (int i = 1; i <= 120; i++) {
        for (int j = 1; j <= 120; j++) {
            dp[j][i] = dp[j-1][i]+dp[j][i-j];
        }
    }
}


int main(){
    solve();
    int toQuery;
    while (cin >> toQuery) {
        cout << dp[toQuery][toQuery] << endl;
    }



    return 0;
}

//Problem F

#include <iostream>

#include <sstream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <map>

#include <list>

#include <stack>

using namespace std;

long long dp[125][125];

void solve(){

memset(dp, 0, sizeof(dp));

for (int i = 1; i <= 120; i++) {

dp[i][0] = 1;

dp[1][i] = 1;

}

for (int i = 1; i <= 120; i++) {

for (int j = 1; j <= 120; j++) {

dp[j][i] = dp[j-1][i]+dp[j][i-j];

}

int main(){

solve();

int toQuery;

while (cin >> toQuery) {

cout << dp[toQuery][toQuery] << endl;

}

return 0;

}

又是一个特定问题了，这个叫拆分数问题（不考虑顺序型）。解法如下（其实是扒来的）：

¤动态规划解题思路：

¤定义状态：dp[x][n]表示只用整数 1~ x 表示出n有多少种方法。

¤状态转移方程：

¤dp[i][n]=dp[i-1][n]+dp[i][n-i]

¤边界条件：

dp[1][k]＝1 (0<=k<=n)

因为对于0~n，只用1去表示的只有一种方法。

其（ren）实（hua）是这样，假如说我们像拆分7，那么我们就是用1～7的数来加合成7了，用1～7表示7可以分开两种看：用1～6表示7，和用1～7表示0，这两种情况，后面那个看起来很sxbk，其实就是7+0啦。然后1～6表示7我们还是不会算，这个又可以分解了，那就是用1～5表示7，和1+6（用1～6表示1），接下来再把1～5表示7拆分为1～4表示7和5+2（用1～5表示2，这会你应该看出来了，5+2中，5不能动只是肯定的，但是2已经不止一种表示方法了），接下来再拆1～4表示7为1～3表示和4+3，然后拆拆拆到1表示7，显然只有一种方法1111111，这样就到达了递推的终点，逐层返回就搞定了。

Tag: 动态规划

HDU 4313 Matrix

题意

思路

代码

Codeforces 461B Appleman and Tree

题意

思路

代码

POJ 3744 Scout YYF I

题意

思路

代码

HDU 4405 Aeroplane chess

题意

思路

代码

POJ 2096 Collecting Bugs

题意

思路

代码

HDU 4035 Maze

题意

思路

相关数学推导

代码

SGU 104 Little shop of flowers

题意

思路

代码

Codeforces 118D Caesar's Legions

题意

思路

接下来上代码

HDU 3466 Proud Merchants

HDU 1028 Ignatius and the Princess III 拆分数问题(顺序无关型)