April 2015 – Page 2

SGU 126 Boxes

April 07, 20152015-04-07hahaschoolLeave a comment

题意

http://www.nocow.cn/index.php/Translate:Sgu/126，翻译版。

思路

我是手写一些找规律，所以我也没办法细讲。

http://www.nocow.cn/index.php/Sgu/126详细题解，说是一个数论题，因为我是找规律所以代码肯定是写不严的，如果你需要严格证明请移步那边。

代码

#include <iostream>
#include <cstdlib>
#include <algorithm>

using namespace std;

int main(){
    long long a = 0,b = 0,sum = 0;
    cin >> a >> b;
    sum = a+b;
    if(a == 0 || b == 0){
        cout << 0 << endl;
    }
    if(sum%2){
        cout << -1 << endl;
        return 0;
    }
    int res = 0;
    long long now = min(a,b);
    while(now != sum/2){
        if(res > 10000){
            cout << -1 << endl;
            return 0;
        }
        res++;
        now *= 2;
        now = min(now,sum-now);
    }
    cout << res+1 << endl;
    return 0;
}

#include <iostream>

#include <cstdlib>

#include <algorithm>

using namespace std;

int main(){

long long a = 0,b = 0,sum = 0;

cin >> a >> b;

sum = a+b;

if(a == 0 || b == 0){

cout << 0 << endl;

}

if(sum%2){

cout << -1 << endl;

return 0;

}

int res = 0;

long long now = min(a,b);

while(now != sum/2){

if(res > 10000){

cout << -1 << endl;

return 0;

}

res++;

now *= 2;

now = min(now,sum-now);

}

cout << res+1 << endl;

return 0;

}

SGU 101 Domino

April 07, 20152015-04-07hahaschoolLeave a comment

题意

给你一堆骨牌，每张骨牌正反两面各有一个0～6范围内的数字，你要做的是确定一种骨牌的排列方式和骨牌的正反似的相邻的两个骨牌的面数字一样。

思路

这种链接多个物体，物体之间通过公共部分链接，这种题是可以转换成图论题做的。那么这个题应该怎么转换？
我们建立0～6这7个节点，每张骨牌就可以看作是链接骨牌上两个数的边，我们要做的就是找到一个路径使得我们可以“一笔”走过所有的边，其实这个叫欧拉通路。
关于欧拉通路，欧拉回路的更多细节，可以参看http://haha.school/guanyuoulahuiluheoulalujing/。
找出欧拉回路的方法就是DFS，但是和以往不同的是我们把处理工作放在下一层返回之后做。同时本题还需要判断欧拉回路是否存在，如果不存在的话要输出无解。

代码

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

vector<pair<int, int> > ljb[7];//first to second id
int n = 0;

bool vis[105];
int res[105];
int now = 0;
void dfs(int currNode){
    for (int i = 0; i < ljb[currNode].size(); i++) {
        if(!vis[abs(ljb[currNode][i].second)]){
            vis[abs(ljb[currNode][i].second)] = true;
            dfs(ljb[currNode][i].first);
            now++;
            res[now] = ljb[currNode][i].second;
        }
    }
}

int main(){
    for(int i = 0;i <= 6;i++)
    ljb[i].clear();
    scanf(" %d",&n);
    int oddpnt = 0;
    for(int i = 1;i <= n;i++){
        int a = 0,b = 0;
        scanf(" %d %d",&a,&b);
        oddpnt = a;
        ljb[a].push_back(make_pair(b,i));
        ljb[b].push_back(make_pair(a,-i));
    }
    int oddcnt = 0,evencnt = 0;
    for (int i = 0; i <= 6; i++) {
            if (ljb[i].size()%2) {
                oddcnt++;
                oddpnt = i;
            }else{
                evencnt++;
            }
    }
    if (evencnt == 7 || oddcnt == 2) {
        memset(vis,0,sizeof(vis));
        memset(res, 0, sizeof(res));
        now = 0;
        dfs(oddpnt);
        if (now != n) {
            printf("No solution\n");
        }else{
            for (int i = n; i >= 1; i--) {
                if (res[i] > 0) {
                    printf("%d +\n",res[i]);
                }else{
                    printf("%d -\n",abs(res[i]));
                }
            }

        }
    }else{
        printf("No solution\n");
    }

    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;

vector<pair<int, int> > ljb[7];//first to second id

int n = 0;

bool vis[105];

int res[105];

int now = 0;

void dfs(int currNode){

for (int i = 0; i < ljb[currNode].size(); i++) {

if(!vis[abs(ljb[currNode][i].second)]){

vis[abs(ljb[currNode][i].second)] = true;

dfs(ljb[currNode][i].first);

now++;

res[now] = ljb[currNode][i].second;

}

int main(){

for(int i = 0;i <= 6;i++)

ljb[i].clear();

scanf(" %d",&n);

int oddpnt = 0;

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

int a = 0,b = 0;

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

oddpnt = a;

ljb[a].push_back(make_pair(b,i));

ljb[b].push_back(make_pair(a,-i));

}

int oddcnt = 0,evencnt = 0;

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

if (ljb[i].size()%2) {

oddcnt++;

oddpnt = i;

}else{

evencnt++;

}

if (evencnt == 7 || oddcnt == 2) {

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

memset(res, 0, sizeof(res));

now = 0;

dfs(oddpnt);

if (now != n) {

printf("No solution\n");

}else{

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

if (res[i] > 0) {

printf("%d +\n",res[i]);

}else{

printf("%d -\n",abs(res[i]));

}

}else{

printf("No solution\n");

}

return 0;

}

关于欧拉回路和欧拉路径

April 07, 20152015-04-07hahaschoolOne Comment

请留意本文转载自http://www.cppblog.com/abilitytao/archive/2010/07/26/121319.html

如果侵犯了您（原作者）的权益请联系我删除，谢谢。

定义：
欧拉回路：每条边恰好只走一次，并能回到出发点的路径
欧拉路径：经过每一条边一次，但是不要求回到起始点

①首先看欧拉回路存在性的判定：

一、无向图
每个顶点的度数都是偶数，则存在欧拉回路。

二、有向图（所有边都是单向的）
每个节顶点的入度都等于出度，则存在欧拉回路。

三.混合图欧拉回路
混合图欧拉回路用的是网络流。
把该图的无向边随便定向，计算每个点的入度和出度。如果有某个点出入度之差为奇数，那么肯定不存在欧拉回路。因为欧拉回路要求每点入度 = 出度，也就是总度数为偶数，存在奇数度点必不能有欧拉回路。
好了，现在每个点入度和出度之差均为偶数。那么将这个偶数除以2，得x。也就是说，对于每一个点，只要将x条边改变方向（入>出就是变入，出>入就是变出），就能保证出 = 入。如果每个点都是出 = 入，那么很明显，该图就存在欧拉回路。
现在的问题就变成了：我该改变哪些边，可以让每个点出 = 入？构造网络流模型。首先，有向边是不能改变方向的，要之无用，删。一开始不是把无向边定向了吗？定的是什么向，就把网络构建成什么样，边长容量上限1。另新建s和t。对于入 > 出的点u，连接边(u, t)、容量为x，对于出 > 入的点v，连接边(s, v)，容量为x（注意对不同的点x不同）。之后，察看是否有满流的分配。有就是能有欧拉回路，没有就是没有。欧拉回路是哪个？查看流值分配，将所有流量非 0（上限是1，流值不是0就是1）的边反向，就能得到每点入度 = 出度的欧拉图。
由于是满流，所以每个入 > 出的点，都有x条边进来，将这些进来的边反向，OK，入 = 出了。对于出 > 入的点亦然。那么，没和s、t连接的点怎么办？和s连接的条件是出 > 入，和t连接的条件是入 > 出，那么这个既没和s也没和t连接的点，自然早在开始就已经满足入 = 出了。那么在网络流过程中，这些点属于“中间点”。我们知道中间点流量不允许有累积的，这样，进去多少就出来多少，反向之后，自然仍保持平衡。
所以，就这样，混合图欧拉回路问题，解了。
②.欧拉路径存在性的判定

一。无向图
一个无向图存在欧拉路径，当且仅当该图所有顶点的度数为偶数或者除了两个度数为奇数外其余的全是偶数。

二。有向图
一个有向图存在欧拉路径，当且仅当该图所有顶点的度数为零或者一个顶点的度数为1，另一个度数为-1，其他顶点的度数为0。

三。混合图欧拉路径
其实整篇文章只有这部分是我写的哈，灰常不好意思，只是网上的同志们写的太好了，实在没有必要重复劳动，不知道大家有没有发现，求欧拉路径的第一步一定是求欧拉回路，在混合图上也不例外，如何判断混合图欧拉回路问题的存在性呢？首先，我们用上文所说的方法判断该图是否存在欧拉回路，如果存在，欧拉路径一定存在。如果欧拉回路不存在，那么我们枚举欧拉路径的起点和终点，连接一条无向边，然后再用最大流判断是否存在欧拉回路即可。

SGU 123 The sum

April 07, 20152015-04-07hahaschoolLeave a comment

题意

打出斐波那契数列前41项。

思路

没啥好说的，入门经典题。对于新手来说，容易跪在直接求斐波那契的题的原因一般是没有采用记忆化的方法（存住之前的每一个值），而是每一次都重新推一遍，这样就超时了。要么就是没有注意到int范围弄爆了，或者把longlong弄爆了（这个时候应该是java大法好）。

代码

#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 fib[43];
long long sum[43];

int main(){
    fib[1] = 1;
    fib[2] = 1;
    for (int i = 3; i <= 41; i++) {
        fib[i] = fib[i-1] + fib[i-2];
    }
    sum[0] = 0;
    for (int i = 1; i <= 41; i++) {
        sum[i] = sum[i-1]+fib[i];
    }
    int toQuery = 0;
    scanf(" %d",&toQuery);
    printf("%lld\n",sum[toQuery]);

    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 fib[43];

long long sum[43];

int main(){

fib[1] = 1;

fib[2] = 1;

for (int i = 3; i <= 41; i++) {

fib[i] = fib[i-1] + fib[i-2];

}

sum[0] = 0;

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

sum[i] = sum[i-1]+fib[i];

}

int toQuery = 0;

scanf(" %d",&toQuery);

printf("%lld\n",sum[toQuery]);

return 0;

}

SGU 108 Self-numbers 2

April 06, 20152015-04-06hahaschoolLeave a comment

题意

http://www.nocow.cn/index.php/Translate:Sgu/108，翻译版，这里不再多说。

思路

这个题刚到手其实都是会写的，但是一般交上去会发现爆内存，原因就是我们用来判定self number的数组开太大了，要想减少空间复杂度只能从这个数组入手，那么我们真的需要那么大的数组么？显然是不用的，通过本题的数据范围可以发现N最大为7位数，即使7位全是9，我们能够更新到的数组区域长度也仅为63个单位，所以我们把bool标记数组开个63长度就够了，开100那更是没问题，这个技巧就是所谓的“滚动数组”。
滚动数组的操作方法有几点：1.通过求余来确定位置 2.使用完当前位置后，要给它初始化为没有使用过的样子以便以后的元素正常使用。
仅仅使用滚动数组还不足以完成这个题，还要注意输出答案的方式，因为数组在滚动，所以你不可能在完成判定之后再输出结果，而是应该边滚动判定，边记录，最后把记录的输出去。
本题有几个坑点：首先你要把输出的目标索引排个序，否则如果数据是乱序的基本都会跪，其次要注意请求的索引中是有重复的，可能一个索引被请求了多次。

代码

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

bool isself[100];
vector<pair<int, int> > goal;
int container[5005];

bool cmp(pair<int, int> a,pair<int, int> b){
    return a.first < b.first;
}

int main(){
    int n = 0,k = 0;
    scanf(" %d %d",&n,&k);
    goal.clear();
    for (int i = 1; i <= k; i++) {
        int tmp = 0;
        scanf(" %d",&tmp);
        goal.push_back(make_pair(tmp, i));
    }
    sort(goal.begin(), goal.end(),cmp);
    memset(isself, true, sizeof(isself));
    memset(container, 0, sizeof(container));
    int cnt = 0;
    int cur = 0;
    for (int i = 1; i <= n; i++) {
        if (isself[i%64]) {
            cnt++;
            while (cnt == goal[cur].first) {
                container[goal[cur].second] = i;
                cur++;
            }
        }
        int tmp = i,sum = i;
        while (tmp != 0) {
            sum += tmp%10;
            tmp /= 10;
        }
        isself[sum%64] = false;
        isself[i%64] = true;
    }
    printf("%d\n",cnt);
    for (int i = 1;i < k; i++) {
        printf("%d ",container[i]);
    }
    printf("%d\n",container[k]);
    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;

bool isself[100];

vector<pair<int, int> > goal;

int container[5005];

bool cmp(pair<int, int> a,pair<int, int> b){

return a.first < b.first;

}

int main(){

int n = 0,k = 0;

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

goal.clear();

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

int tmp = 0;

scanf(" %d",&tmp);

goal.push_back(make_pair(tmp, i));

}

sort(goal.begin(), goal.end(),cmp);

memset(isself, true, sizeof(isself));

memset(container, 0, sizeof(container));

int cnt = 0;

int cur = 0;

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

if (isself[i%64]) {

cnt++;

while (cnt == goal[cur].first) {

container[goal[cur].second] = i;

cur++;

}

int tmp = i,sum = i;

while (tmp != 0) {

sum += tmp%10;

tmp /= 10;

}

isself[sum%64] = false;

isself[i%64] = true;

}

printf("%d\n",cnt);

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

printf("%d ",container[i]);

}

printf("%d\n",container[k]);

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;

}

服务器已经更换～

April 02, 20152015-04-02hahaschoolLeave a comment

现在使用的是conoha（为啥换大家都懂）。

conoha挺萌的，就是爱抽风。

然后试着改了下主题，但是这个主题手机端有些表现不如24，看来需要一定措施。

新的nginx缓存可能需要更多的调教。

旧服务器可能还会运作一段时间，访问地址为old.haha.school

SGU 107 987654321 problem

April 01, 20152015-04-01hahaschoolLeave a comment

题意

给你n，让你输出n位数中平方后尾数是987654321的数的个数。

思路

一个数，只考虑最后i位，那么这个数平方之后的最后i位和这个数的最后i位平方后的最后i位相同，所以我们只要考虑1～9位数中谁的平方最后9位是987654321就可以了，本地打个表，发现只有8个数符合要求，接下来，对于10位数，我们就有98=72种组合对于11位数就是908=720种组合，这样我们就发现了，超过10位数的话，就在73后面补上n-10个零就行了，这样大数时也搞定了。

代码

#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 a = 0;
    scanf("%d",&a);
    if (a <= 8) {
        printf("0n");
    }else if(a == 9){
        printf("8n");
    }else{
        printf("72");
        for (int i = 10; i < a; i++) {
            printf("0");
        }
        printf("n");
    }

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

int a = 0;

scanf("%d",&a);

if (a <= 8) {

printf("0n");

}else if(a == 9){

printf("8n");

}else{

printf("72");

for (int i = 10; i < a; i++) {

printf("0");

}

printf("n");

}

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;

}

Month: April 2015

SGU 126 Boxes

题意

思路

代码

SGU 101 Domino

题意

思路

代码

关于欧拉回路和欧拉路径

SGU 123 The sum

题意

思路

代码

SGU 108 Self-numbers 2

题意

思路

代码

HDU 4035 Maze

题意

思路

相关数学推导

代码

服务器已经更换～

SGU 107 987654321 problem

题意

思路

代码

SGU 104 Little shop of flowers

题意

思路

代码