HDU – Page 2 – hahaschool

15多校2-9/HDU 5308 I Wanna Become A 24-Point Master

July 23, 20152015-07-23hahaschool2 Comments

更新

根据出题人的回复，问题应该已经修复了，本文代码中的PATCH部分可以忽略。关于原来出现的问题的证明也已经失效，敬请留意。

题意

给出一个数字n，问你如果给你n个n，你要怎么样才能利用加减乘除运算给算成24呢？注意，没个数字只能使用一次，所有的数字必须都要用到。你要按照题里面介绍的特别的表示方法把你的解法表示出来。除法是可以出分数的，因为是SPJ，应该可以过。

思路

我个人不太认同出题人题解里面给出的手算4～15的所有情况，对于较大的数再机智得直接消除凑24，因为手算的太多了。

我的思路是对于比较小的情况，即n <= 27的时候，可以直接利用dfs找出答案。因为题目给出的表示方法其实意外地适合dfs的搜索过程，我们不断的枚举下一个操作，即从当前没用过的数里面选出两个，然后尝试加减乘除，每一次尝试就是改变当前数组尾部的值，同时做好标记进入下一层。只要搜索成功，我们就可以在dfs的退出过程中将路径保存下来，开一个stack，把这些个结果压进去，输出的时候弹出来，顺序就正好是正序了。

对于比较大的情况，事情就变得非常简单，假如说现在的n = k，那么只要找出24个相同的数k，加到一起，就是24 * k了，然后再额外拿一个k，做一下商，就得到了24，对于多出来的数，我们可以找两个k做一下差得0，然后用得到的0去乘上下一个多余的数，最后剩下一个0，和刚才的24加一下，多余的数也消耗掉了。

注意点

做这个题的时候发生了两处失误，首先是dfs的时候，范围设置的不正确，两层的循环都应该是从1开始的，原来外层从1开始而内层却是从i+1开始(i是外层的循环变量)，这样显然丢解了，而且搜索速度也拖慢了。

其次是题目中要求每个数只可以用一次，结果我偷懒把一个0跟好多哥数字去乘了，这样肯定就错了。

然后dfs应该采取一些必要的优化，比如说跳过重复的区段（剪枝），如果不做的话可能超时。如果实在没办法，打表也可以，反正才24种情况，并不会被拒绝提交。

然而还是没过

折腾了一下午后发现很有可能这个题的评测器在实现上有漏洞，通过排(feng)除(kuang)法(jiao)，发现有3组数据没有通过评测器，但是确实是正确的。

n = 13

1 + 2

3 + 4

5 + 6

7 + 8

9 + 10

11 + 12

13 + 14

15 + 16

17 + 20

21 - 22

18 / 23

19 + 24

n = 14

1 + 2

3 + 4

5 + 6

7 + 8

9 + 10

11 + 12

13 + 14

15 + 16

17 + 18

19 * 20

22 + 23

24 - 25

26 / 21

n = 22

1 + 2

3 + 4

5 + 6

7 + 8

9 + 10

11 + 12

13 + 14

15 + 16

17 + 18

19 + 20

21 + 22

23 + 24

25 + 26

27 + 28

29 + 30

31 * 32

33 + 34

35 - 39

36 / 40

38 / 37

42 - 41

如果数据确实不符合题意，请与我跟进，谢谢。

代码

为了过，最后没有办法特殊对待给上面三组数据打了补丁。

#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;

int seq[100];
bool vis[100];
int n = 0;
struct expr{
    int a,b;
    char op;
    expr(int _a, char _op,int _b){
        a = _a;
        b = _b;
        op = _op;
    }
};
stack<expr> resstk;

bool dfs(int dep){
    if (dep == 2*n) {
        if (seq[dep-1] == 24) {
            return true;
        }else{
            return false;
        }
    }
    int prev = -909303;
    for (int i = 1; i < dep; i++) {
        if (!vis[i]) {
            if (seq[i] == prev) {
                continue;
            }else{
                prev = seq[i];
            }
            vis[i] = true;
            int inner_prev = -909303;
            for (int j = 1; j < dep; j++) {
                if (!vis[j]) {
                    if (seq[j] == inner_prev) {
                        continue;
                    }else{
                        inner_prev = seq[j];
                    }
                    vis[j] = true;
                    seq[dep] = seq[i] + seq[j];
                    if (dfs(dep+1)) {
                        resstk.push(expr(i,'+',j));
                        return true;
                    }else{
                        seq[dep] = seq[i] - seq[j];
                        if (dfs(dep+1)) {
                            resstk.push(expr(i,'-',j));
                            return true;
                        }else{
                            seq[dep] = seq[i] * seq[j];
                            if (dfs(dep+1)) {
                                resstk.push(expr(i,'*',j));
                                return true;
                            }else{
                                if (seq[j] != 0 && seq[i] % seq[j] == 0) {
                                    seq[dep] = seq[i] / seq[j];
                                    if (dfs(dep+1)) {
                                        resstk.push(expr(i,'/',j));
                                        return true;
                                    }else{
                                        vis[j] = false;
                                        seq[dep] = 0;
                                    }
                                }else{
                                    vis[j] = false;
                                    seq[dep] = 0;
                                }
                            }
                        }
                    }
                }

            }
            vis[i] = false;
        }
    }
    return false;
}
void init(){
    memset(seq, 0, sizeof(seq));
    memset(vis, 0, sizeof(vis));
    while (!resstk.empty()) {
        resstk.pop();
    }
}


void print(){
    while (!resstk.empty()) {
        expr &nowExpr = resstk.top();
        printf("%d %c %d\n",nowExpr.a,nowExpr.op,nowExpr.b);
        resstk.pop();
    }

}
void printSpec(){
    printf("1 - 2\n");
    int cur = n+2,pos = 3,zero = n+1;
    for (int i = 1; i <= n - 27; i++,pos++,cur++,zero++) {
        printf("%d * %d\n",zero,pos);
    }
    for (int i = 1; i <= 12; i++,pos+=2) {
        printf("%d + %d\n",pos,pos+1);
    }
    for (; cur <= 2*n-4;cur += 2) {
        printf("%d + %d\n",cur,cur+1);
    }
    printf("%d / %d\n",2*n-3,n);
    printf("%d + %d\n",2*n-2,zero);

}

int main(){
    while (scanf("%d",&n)!=EOF){
        if (n > 27) {
            printSpec();
            continue;
        }
        /*
         PATCH FOR THE DEFECTIVE SPJ
         */
        if (n == 22){
            printf("1 + 2\n"); printf("3 + 4\n"); printf("5 + 6\n"); printf("7 + 8\n"); printf("%d + 9\n",n+1);
            printf("%d / 10\n",n+2); printf("%d / 11\n",n+3); printf("%d / 12\n",n+4); printf("%d / 13\n",n+5);
            printf("%d * %d\n",n+6,n+7); printf("%d * %d\n",n+8,n+9); printf("%d * %d\n",n+10,n+11); printf("14 - 15\n");
            int now=n+13; for (int i=16;i<=n;i++){printf("%d * %d\n",i,now); now++;} printf("%d + %d\n",n+12,now); continue;
        }
        if (n == 13 || n == 14){
            printf("1 + 2\n");
            for (int i=1;i<=n*2-24;i++) printf("%d / %d\n",i*2+1,i*2+2); int num=n*4-46;
            int now=n+1+n*2-24;
            if (n!=12){
                printf("%d - %d\n",n+1,n+2); now++;
                for (int i=2;i<=n*2-24;i++){printf("%d - %d\n",now,n+1+i); now++;}
            }
            int k1=now;
            printf("%d - %d\n",num+1,num+2); num+=3; now++;
            for (int i=num;i<=n;i++){printf("%d * %d\n",i,now); now++;}
            printf("%d + %d\n",k1,now); continue;
        }
        /*
         END OF PATCH
         */
        if (n >= 1) {
            init();
            for (int i = 1; i <= n; i++) {
                seq[i] = n;
            }
            dfs(n+1);
            if (!resstk.empty()) {
                print();
            }else{
                puts("-1");
            }
            continue;
        }
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

#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;

int seq[100];

bool vis[100];

int n = 0;

struct expr{

int a,b;

char op;

expr(int _a, char _op,int _b){

a = _a;

b = _b;

op = _op;

}

};

stack<expr> resstk;

bool dfs(int dep){

if (dep == 2*n) {

if (seq[dep-1] == 24) {

return true;

}else{

return false;

}

int prev = -909303;

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

if (!vis[i]) {

if (seq[i] == prev) {

continue;

}else{

prev = seq[i];

}

vis[i] = true;

int inner_prev = -909303;

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

if (!vis[j]) {

if (seq[j] == inner_prev) {

continue;

}else{

inner_prev = seq[j];

}

vis[j] = true;

seq[dep] = seq[i] + seq[j];

if (dfs(dep+1)) {

resstk.push(expr(i,'+',j));

return true;

}else{

seq[dep] = seq[i] - seq[j];

if (dfs(dep+1)) {

resstk.push(expr(i,'-',j));

return true;

}else{

seq[dep] = seq[i] * seq[j];

if (dfs(dep+1)) {

resstk.push(expr(i,'*',j));

return true;

}else{

if (seq[j] != 0 && seq[i] % seq[j] == 0) {

seq[dep] = seq[i] / seq[j];

if (dfs(dep+1)) {

resstk.push(expr(i,'/',j));

return true;

}else{

vis[j] = false;

seq[dep] = 0;

}

}else{

vis[j] = false;

seq[dep] = 0;

}

vis[i] = false;

}

return false;

}

void init(){

memset(seq, 0, sizeof(seq));

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

while (!resstk.empty()) {

resstk.pop();

}

void print(){

while (!resstk.empty()) {

expr &nowExpr = resstk.top();

printf("%d %c %d\n",nowExpr.a,nowExpr.op,nowExpr.b);

resstk.pop();

}

void printSpec(){

printf("1 - 2\n");

int cur = n+2,pos = 3,zero = n+1;

for (int i = 1; i <= n - 27; i++,pos++,cur++,zero++) {

printf("%d * %d\n",zero,pos);

}

for (int i = 1; i <= 12; i++,pos+=2) {

printf("%d + %d\n",pos,pos+1);

}

for (; cur <= 2*n-4;cur += 2) {

printf("%d + %d\n",cur,cur+1);

}

printf("%d / %d\n",2*n-3,n);

printf("%d + %d\n",2*n-2,zero);

}

int main(){

while (scanf("%d",&n)!=EOF){

if (n > 27) {

printSpec();

continue;

}

PATCH FOR THE DEFECTIVE SPJ

if (n == 22){

printf("1 + 2\n"); printf("3 + 4\n"); printf("5 + 6\n"); printf("7 + 8\n"); printf("%d + 9\n",n+1);

printf("%d / 10\n",n+2); printf("%d / 11\n",n+3); printf("%d / 12\n",n+4); printf("%d / 13\n",n+5);

printf("%d * %d\n",n+6,n+7); printf("%d * %d\n",n+8,n+9); printf("%d * %d\n",n+10,n+11); printf("14 - 15\n");

int now=n+13; for (int i=16;i<=n;i++){printf("%d * %d\n",i,now); now++;} printf("%d + %d\n",n+12,now); continue;

}

if (n == 13 || n == 14){

printf("1 + 2\n");

for (int i=1;i<=n*2-24;i++) printf("%d / %d\n",i*2+1,i*2+2); int num=n*4-46;

int now=n+1+n*2-24;

if (n!=12){

printf("%d - %d\n",n+1,n+2); now++;

for (int i=2;i<=n*2-24;i++){printf("%d - %d\n",now,n+1+i); now++;}

}

int k1=now;

printf("%d - %d\n",num+1,num+2); num+=3; now++;

for (int i=num;i<=n;i++){printf("%d * %d\n",i,now); now++;}

printf("%d + %d\n",k1,now); continue;

}

END OF PATCH

if (n >= 1) {

init();

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

seq[i] = n;

}

dfs(n+1);

if (!resstk.empty()) {

print();

}else{

puts("-1");

}

continue;

}

return 0;

}

标准答案里边很豪放地用了分数，正常来讲评测器应该是接受分数的，但不知道为什么不接受我这个调换位置保证不出现分数的答案了，真的很怪。我自己写了一个检查我自己答案的评测器，没有提供对分数的支持，但是评测器会在发现出现分数的时候报错，因为我的答案是已经调换顺序保证不出分数的了，此外也检查了每个数字的使用情况，保证和题意一致。

#include <iostream>
#include <cstring>

using namespace std;
int seq[200000];
int cnt[200000];

int main(int argc, const char * argv[]) {
    freopen("testdata.1009", "r", stdin);
    memset(seq, 0, sizeof(seq));
    int n = 0;
    while (cin >> n) {
        if (n <= 3) {
            int tmp;
            cin >> tmp;
            continue;
        }
        for (int i = 1; i <= n; i++) {
            seq[i] = n;
        }
        memset(cnt, 0, sizeof(cnt));
        for (int i = 1; i <= n-1; i++) {
            int a,b;
            char op;
            cin >> a >> op >> b;
            cnt[a]++,cnt[b]++;
            switch (op) {
                case '+':
                    seq[i+n] = seq[a] + seq[b];
                    break;
                case '-':
                    seq[i+n] = seq[a] - seq[b];
                    break;
                case '*':
                    seq[i+n] = seq[a] * seq[b];
                    break;
                case '/':
                    if (seq[a] % seq[b]) {
                        cout << "WRONG ANSWER AT " << n << endl;
                        return 998;
                    }
                    seq[i+n] = seq[a] / seq[b];
                    break;
                default:
                    break;
            }
        }if (seq[2*n-1] == 24) {
            for (int i = 1; i <= 2*n-2; i++) {
                if (cnt[i] != 1) {
                    cout << "WRONG ANSWER AT " << n << endl;
                    return 998;
                }
            }
        }else{
            cout << "WRONG ANSWER AT " << n << endl;
            return 998;
        }
        cout << "CORRECT AT " << n << endl;
    }
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int seq[200000];

int cnt[200000];

int main(int argc, const char * argv[]) {

freopen("testdata.1009", "r", stdin);

memset(seq, 0, sizeof(seq));

int n = 0;

while (cin >> n) {

if (n <= 3) {

int tmp;

cin >> tmp;

continue;

}

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

seq[i] = n;

}

memset(cnt, 0, sizeof(cnt));

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

int a,b;

char op;

cin >> a >> op >> b;

cnt[a]++,cnt[b]++;

switch (op) {

case '+':

seq[i+n] = seq[a] + seq[b];

break;

case '-':

seq[i+n] = seq[a] - seq[b];

break;

case '*':

seq[i+n] = seq[a] * seq[b];

break;

case '/':

if (seq[a] % seq[b]) {

cout << "WRONG ANSWER AT " << n << endl;

return 998;

}

seq[i+n] = seq[a] / seq[b];

break;

default:

break;

}

}if (seq[2*n-1] == 24) {

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

if (cnt[i] != 1) {

cout << "WRONG ANSWER AT " << n << endl;

return 998;

}

}else{

cout << "WRONG ANSWER AT " << n << endl;

return 998;

}

cout << "CORRECT AT " << n << endl;

}

return 0;

}

从1开始测了1个GB的数据，没发现问题，如果评测器有问题，请跟进，谢谢。

如果你还是不相信我

下面是官方题解：

虽然很蛋疼，写这么多其实就是为了让这么个玩意别再坑更多的人了。

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;

}

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;

}

HDU 4961 Boring Sum

March 01, 20152015-03-01hahaschoolLeave a comment

#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;

#define MAXN 100005

int a[MAXN],b[MAXN],c[MAXN];
vector<int> d[MAXN];

void gen(){
    for (int i = 1; i < MAXN; i++) {
        for (int j = 1; i * j < MAXN; j++) {
            d[i*j].push_back(i);
        }
    }
}

int vis[MAXN];
void solve(int n){
    //->
    memset(vis, -1, sizeof(vis));
    for (int i = 1;i <= n; i++) {
        int now = a[i];
        if (vis[now] != -1) {
            b[i] = vis[now];
        }
        for (int j = 0;j < d[now].size(); j++) {
            vis[d[now][j]] = now;
        }
        if (b[i] == -1) {
            b[i] = now;
        }
    }
    //<-
    memset(vis, -1, sizeof(vis));
    for (int i = n; i >= 1; i--) {
        int now = a[i];
        if (vis[now] != -1) {
            c[i] = vis[now];
        }
        for (int j = 0; j < d[now].size(); j++) {
            vis[d[now][j]] = now;
        }
        if (c[i] == -1) {
            c[i] = now;
        }
    }
}

int main(){
    gen();
    int n = 0;
    while(scanf(" %d",&n) != EOF && n){
        memset(a, -1, sizeof(a));
        memset(b, -1, sizeof(b));
        memset(c, -1, sizeof(c));
        for (int i = 1; i <= n; i++) {
            scanf(" %d",&a[i]);
        }
        solve(n);
        long long res = 0;
        for (int i = 1; i <= n; i++) {
            res += (long long)b[i] * (long long)c[i];
        }
        printf("%lldn",res);
    }
    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;

#define MAXN 100005

int a[MAXN],b[MAXN],c[MAXN];

vector<int> d[MAXN];

void gen(){

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

for (int j = 1; i * j < MAXN; j++) {

d[i*j].push_back(i);

}

int vis[MAXN];

void solve(int n){

//->

memset(vis, -1, sizeof(vis));

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

int now = a[i];

if (vis[now] != -1) {

b[i] = vis[now];

}

for (int j = 0;j < d[now].size(); j++) {

vis[d[now][j]] = now;

}

if (b[i] == -1) {

b[i] = now;

}

//<-

memset(vis, -1, sizeof(vis));

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

int now = a[i];

if (vis[now] != -1) {

c[i] = vis[now];

}

for (int j = 0; j < d[now].size(); j++) {

vis[d[now][j]] = now;

}

if (c[i] == -1) {

c[i] = now;

}

int main(){

gen();

int n = 0;

while(scanf(" %d",&n) != EOF && n){

memset(a, -1, sizeof(a));

memset(b, -1, sizeof(b));

memset(c, -1, sizeof(c));

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

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

}

solve(n);

long long res = 0;

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

res += (long long)b[i] * (long long)c[i];

}

printf("%lldn",res);

}

return 0;

}

智商鸿沟不可越系列。。。

思路是这样：首先对于1～100000每一个数生成一个约数表，方便以后查询，我们再建立一个int数组为vis，尺寸100000。接下来对于输入的数组，从左往右扫描，对于每一个数，如果vis[这个数]有值，说明当前数左端有倍数存在，最近的倍数就是这个vis值，没有的话，就是这个数本身，接下来读取当前数的每一个约数，对于每一个约数，当前数都是他们的倍数，所以更新vis[每一个约数]的值为当前数就可以了。
接下来方向反过来，从右到左扫描，算出c值，最统一出答案，小心别爆了int就行。

HDU 1730 Northcott Game

February 28, 20152015-02-28hahaschoolLeave a comment

//HDU 1730 Northcott Game
//FAILED
/*
#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 main(){
    int n = 0,m = 0;
    while (cin >> n >> m) {
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            int a = 0,b = 0;
            cin >> a >> b;
            if (abs(a-b)!=1) {
                cnt++;
            }
        }
        if (cnt%2) {
            cout << "I WIN!" << endl;
        }else{
            cout << "BAD LUCK!" << endl;
        }
    }
    return 0;
}*/
//AC
/*
#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 main(){
    int n = 0,m = 0;
    while (cin >> n >> m) {
        int nim = 0;
        for (int i = 1; i <= n; i++) {
            int a = 0,b = 0;
            cin >> a >> b;
            nim ^= abs(a-b)-1;
        }
        if (!nim) {
            cout << "BAD LUCK!" << endl;
        }else{
            cout << "I WIN!" << endl;
  ]      }
    }
    return 0;
}

//HDU 1730 Northcott Game

//FAILED

#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 main(){

int n = 0,m = 0;

while (cin >> n >> m) {

int cnt = 0;

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

int a = 0,b = 0;

cin >> a >> b;

if (abs(a-b)!=1) {

cnt++;

}

if (cnt%2) {

cout << "I WIN!" << endl;

}else{

cout << "BAD LUCK!" << endl;

}

return 0;

}*/

//AC

#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 main(){

int n = 0,m = 0;

while (cin >> n >> m) {

int nim = 0;

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

int a = 0,b = 0;

cin >> a >> b;

nim ^= abs(a-b)-1;

}

if (!nim) {

cout << "BAD LUCK!" << endl;

}else{

cout << "I WIN!" << endl;

] }

}

return 0;

}

我把做错了的也发出来，一种典型的做错了的思路就是：先查Tom和Jerry的初始位置有空隙的行的个数，如果是奇数就是一种情况偶数另外一种情况，这个是不正确的。

正确的思路：我们可以把问题转化为没行空隙的大小就是每堆石子的个数，双方每轮任选一堆，取少则为1多则任意大枚石子，先取完获胜，这就是典型的Nim博弈。所以把每一行空隙大小（abs(a-b)-1）挨个xor，然后看看是不是0就行了。

HDU 4112 Break the Chocolate

February 26, 20152015-02-26hahaschoolLeave a comment

#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;

long long f(long long a){
    long long res = 0;
    for (long long i = 1; ; i *= 2) {
        if (i >= a) {
            return res;
        }
        res++;
    }
}


int main(){
    int caseCnt;
    cin >> caseCnt;
    for (int i = 1; i <= caseCnt; i++) {
        long long a = 0,b = 0,c = 0;
        cin >> a >> b >> c;
        long long res1 = a*b*c-1;
        long long res2 = f(a)+f(b)+f(c);
        cout << "Case #" << i << ": " << res1 << ' ' << res2 << 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;

long long f(long long a){

long long res = 0;

for (long long i = 1; ; i *= 2) {

if (i >= a) {

return res;

}

res++;

}

int main(){

int caseCnt;

cin >> caseCnt;

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

long long a = 0,b = 0,c = 0;

cin >> a >> b >> c;

long long res1 = a*b*c-1;

long long res2 = f(a)+f(b)+f(c);

cout << "Case #" << i << ": " << res1 << ' ' << res2 << endl;

}

return 0;

}

利用思维陷阱虐菜的水题（然后就逼视了ˊ_>ˋ），用刀切那个地方不能头脑简单，如果有一个1 1 8的巧克力，只要切3下就可以（半分，放一起再半分，放一起再半分）。可以先从1维入手，发现二进制类似的这个取值规律，然后升维考虑。

HDU 4920 Matrix Multiplication

February 23, 20152015-02-23hahaschoolLeave a comment

#include <string.h>
#include <stdio.h>

int MATSIZE = 801;
int mata[810][810];
int matb[810][810];
int matc[810][810];
int main(){
    while (scanf("%d",&MATSIZE) != EOF) {
        int i,j,k;
        for (i = 0;i < MATSIZE; i++) {
            for (j = 0; j < MATSIZE; j++) {
                scanf("%d",&mata[i][j]);
                mata[i][j] %= 3;
            }
        }
        for (i = 0;i < MATSIZE; i++) {
            for (j = 0; j < MATSIZE; j++) {
                scanf("%d",&matb[i][j]);
                matb[i][j] %= 3;
            }
        }
        memset(matc, 0, sizeof(matc));
        for(i = 0;i < MATSIZE;i++){
            for(j = 0;j < MATSIZE;j++){
                if (matb[i][j] == 0) {
                    continue;
                }
                for(k = 0;k < MATSIZE;k++){
                    matc[k][j] += mata[k][i] * matb[i][j];
                }
            }
        }
        for (i = 0;i < MATSIZE; i++) {
            for (j = 0; j < MATSIZE-1; j++) {
                printf("%d ",(matc[i][j]+3)%3);
            }
            printf("%dn",(matc[i][MATSIZE-1]+3)%3);
        }
    }
    return 0;
}

#include <string.h>

#include <stdio.h>

int MATSIZE = 801;

int mata[810][810];

int matb[810][810];

int matc[810][810];

int main(){

while (scanf("%d",&MATSIZE) != EOF) {

int i,j,k;

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

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

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

mata[i][j] %= 3;

}

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

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

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

matb[i][j] %= 3;

}

memset(matc, 0, sizeof(matc));

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

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

if (matb[i][j] == 0) {

continue;

}

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

matc[k][j] += mata[k][i] * matb[i][j];

}

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

for (j = 0; j < MATSIZE-1; j++) {

printf("%d ",(matc[i][j]+3)%3);

}

printf("%dn",(matc[i][MATSIZE-1]+3)%3);

}

return 0;

}

#include <string.h>
#include <stdio.h>

int MATSIZE = 801;
int mata[810][810];
int matb[810][810];
int matc[810][810];
int main(){
    while (scanf("%d",&MATSIZE) != EOF) {
        int i,j,k;
        for (i = 0;i < MATSIZE; i++) {
            for (j = 0; j < MATSIZE; j++) {
                scanf("%d",&mata[i][j]);
                mata[i][j] %= 3;
            }
        }
        for (i = 0;i < MATSIZE; i++) {
            for (j = 0; j < MATSIZE; j++) {
                scanf("%d",&matb[i][j]);
                matb[i][j] %= 3;
            }
        }
        memset(matc, 0, sizeof(matc));
     for(k = 0;k < MATSIZE;k++){
        for(i = 0;i < MATSIZE;i++){
            for(j = 0;j < MATSIZE;j++){
                    matc[i][j] += mata[i][k] * matb[k][j];
                }
            }
        }
        for (i = 0;i < MATSIZE; i++) {
            for (j = 0; j < MATSIZE-1; j++) {
                printf("%d ",(matc[i][j]+3)%3);
            }
            printf("%dn",(matc[i][MATSIZE-1]+3)%3);
        }
    }
    return 0;
}

#include <string.h>

#include <stdio.h>

int MATSIZE = 801;

int mata[810][810];

int matb[810][810];

int matc[810][810];

int main(){

while (scanf("%d",&MATSIZE) != EOF) {

int i,j,k;

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

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

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

mata[i][j] %= 3;

}

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

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

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

matb[i][j] %= 3;

}

memset(matc, 0, sizeof(matc));

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

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

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

matc[i][j] += mata[i][k] * matb[k][j];

}

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

for (j = 0; j < MATSIZE-1; j++) {

printf("%d ",(matc[i][j]+3)%3);

}

printf("%dn",(matc[i][MATSIZE-1]+3)%3);

}

return 0;

}

上面的T下面的过，开始我还以为是TMD被逗了，直到我看到了这个：

http://blog.csdn.net/a775700879/article/details/11750703

然后我就吓尿了。。。10倍的效率差距

上面的那个，是利用了乘法式子中可以通过调整固定一个值，如果这个值是0就可以剪枝不循环这次的第三重直接往下走了，但是收效甚微。

getchar()的输入挂。。。那货我伺候不来，感觉太玄了没有写。

而下面那个是把原来i，j，k循环中的k拿了出来做了第一重，这样带来的变化是原来第三重循环要跳k次行，现在的话第三重循环不再跳行。多维数组是线性存储的，CPU缓存比较小会经常更新，跳列的话，就很有可能无法利用CPU缓存的优势（注意缓存直连CPU，比内存还要快），因为当跳到下一行的时候，刚才那一行可能就被从CPU缓存中清除了，相当于第三重循环里面没有用到CPU缓存机能。

所以当疯狂访问数组的时候，时间卡的很丧病，就要看看是不把CPU缓存机能给浪费了。

HDU 1142 A Walk Through the Forest

January 30, 20152015-01-30hahaschoolLeave 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;
#define MAXN 0x3f3f3f3f

int cost[1005][1005];
int dis[1005];
bool vis[1005];
void dijkstra(int n){
    memset(dis, MAXN, sizeof(dis));
    memset(vis, false, sizeof(vis));
    dis[2] = 0;
    while (true) {
        int cur = 0,mindis = MAXN;
        for (int i = 1; i <= n; i++) {
            if (vis[i]) {
                continue;
            }
            if (dis[i] < mindis) {
                mindis = dis[i];
                cur = i;
            }
        }
        if (!cur) {
            break;
        }
        vis[cur] = true;
        for (int i = 1; i <= n; i++) {
            if (vis[i]) {
                continue;
            }
            if (cost[cur][i]!=MAXN && dis[cur]+cost[cur][i] < dis[i]) {
                dis[i] = cost[cur][i]+dis[cur];
            }
        }
    }
}

int cnt[1005];
int dfs(int currNode,int n){
    if (cnt[currNode] != -1) {
        return cnt[currNode];
    }
    if (currNode == 2) {
        return 1;
    }
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        if (cost[currNode][i] == MAXN) {
            continue;
        }
        if (dis[currNode] > dis[i]) {
            sum += dfs(i,n);
        }
    }
    return cnt[currNode] = sum;
}


int main(){
    int n = 0, m = 0;
    while (scanf(" %d",&n) != EOF && n) {
        scanf(" %d",&m);
        memset(cost, MAXN, sizeof(cost));
        for (int i = 1; i <= n; i++) {
            cost[i][i] = 0;
        }
        for (int i = 1; i <= m; i++) {
            int a = 0,b = 0,c = 0;
            scanf(" %d %d %d",&a,&b,&c);
            cost[a][b] = c;
            cost[b][a] = c;
        }
        dijkstra(n);
        memset(cnt, -1, sizeof(cnt));
        cout << dfs(1,n) << 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;

#define MAXN 0x3f3f3f3f

int cost[1005][1005];

int dis[1005];

bool vis[1005];

void dijkstra(int n){

memset(dis, MAXN, sizeof(dis));

memset(vis, false, sizeof(vis));

dis[2] = 0;

while (true) {

int cur = 0,mindis = MAXN;

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

if (vis[i]) {

continue;

}

if (dis[i] < mindis) {

mindis = dis[i];

cur = i;

}

if (!cur) {

break;

}

vis[cur] = true;

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

if (vis[i]) {

continue;

}

if (cost[cur][i]!=MAXN && dis[cur]+cost[cur][i] < dis[i]) {

dis[i] = cost[cur][i]+dis[cur];

}

int cnt[1005];

int dfs(int currNode,int n){

if (cnt[currNode] != -1) {

return cnt[currNode];

}

if (currNode == 2) {

return 1;

}

int sum = 0;

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

if (cost[currNode][i] == MAXN) {

continue;

}

if (dis[currNode] > dis[i]) {

sum += dfs(i,n);

}

return cnt[currNode] = sum;

}

int main(){

int n = 0, m = 0;

while (scanf(" %d",&n) != EOF && n) {

scanf(" %d",&m);

memset(cost, MAXN, sizeof(cost));

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

cost[i][i] = 0;

}

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

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

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

cost[a][b] = c;

cost[b][a] = c;

}

dijkstra(n);

memset(cnt, -1, sizeof(cnt));

cout << dfs(1,n) << endl;

}

return 0;

}

这个题数据好像有坑，如果用vector实现的邻接表会WAWAWA。。。嗯

然后题意那个sxbk的英语也是醉人，要是理解成最短路有多少条就哈哈了，应该是使到2节点的最短距离递减的节点序列有多少条。

然后你理解对了题意，又很脸好地用了邻接矩阵，嗯，估计还会T一阵子，原因是这个题还要卡DFS的优化问题，要使用记忆化搜索。

把这三点都注意了就能A了。（如果数据不坑，其实真是个好题）

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

15多校2-9/HDU 5308 I Wanna Become A 24-Point Master

更新

题意

思路

注意点

然而还是没过

代码

如果你还是不相信我

HDU 4405 Aeroplane chess

题意

思路

代码

HDU 4035 Maze

题意

思路

相关数学推导

代码

HDU 4961 Boring Sum

HDU 1730 Northcott Game

HDU 4112 Break the Chocolate

HDU 4920 Matrix Multiplication

HDU 1142 A Walk Through the Forest

HDU 3466 Proud Merchants

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