标签归档：洛谷

洛谷 P1801 黑匣子_NOI导刊2010提高（06）

发表评论

异常清晰，自己花了好长时间想出来的，继续加油！

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
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
struct BlackBox {
private:
    priority_queue<ll,vector<ll>,greater<ll> > minHeap;
    priority_queue<ll> maxHeap;
public:
    void add(ll num) {
        if (maxHeap.empty())minHeap.push(num);
        else if (num < maxHeap.top()) {
            minHeap.push(maxHeap.top());
            maxHeap.pop();
            maxHeap.push(num);
        }
        else minHeap.push(num);
    }
    ll get() {
        ll re = minHeap.top();
        maxHeap.push(minHeap.top());
        minHeap.pop();
        return re;
    }
}BB;
int m, n;
ll arr1[200005], arr2[200005];
ll arr2Ptr = 1;
int main() {
    ios::sync_with_stdio(false);
    cin >> m >> n;
    for (int i = 1; i <= m; i++) cin >> arr1[i];
    for (int i = 1; i <= n; i++)cin >> arr2[i];
    for (int i = 1; i <= m; i++) {
        BB.add(arr1[i]);
        while (arr2[arr2Ptr] == i) {
            cout << BB.get() << endl;
            arr2Ptr++;
        }
    }
}

洛谷 P4779 【模板】单源最短路径（标准版）

发表评论

SPFA 40;Dijkstra AC.
这个Dijkstra是没问题的版本，有问题的参见：https://renjikai.com/luogu-p1339/

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int t, c, ts;
struct edge {
    long long v, w;
    edge(int vv, int ww) { v = vv; w = ww; }
    bool operator < (const edge& e2) const{
        return w > e2.w;
    }
};
vector<edge> edges[100005];
long long dis[100005];
bool inqueue[100005];
bool visited[100005];
void SPFA() {
    queue<int> q;
    dis[ts] = 0;
    inqueue[ts] = true;
    q.push(ts);
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        inqueue[node] = false;
        for (int i = 0; i < edges[node].size(); i++) {
            if (dis[edges[node][i].v] > dis[node] + edges[node][i].w) {
                dis[edges[node][i].v] = dis[node] + edges[node][i].w;
                if (!inqueue[edges[node][i].v])q.push(edges[node][i].v);
            }
        }
    }
}
void dijkstra() {
    priority_queue<edge> pq;
        dis[ts] = 0;
    pq.push(edge(ts,0));
    while (!pq.empty()) {
        edge e = pq.top();
        pq.pop();
        if (visited[e.v])continue;
        visited[e.v] = true;
        //dis[e.v] = e.w;
        for (int i = 0; i < edges[e.v].size(); i++) {
            if (!visited[edges[e.v][i].v] && dis[edges[e.v][i].v] > dis[e.v] + edges[e.v][i].w) {
                //有可能存在一种情况：虽然没有轮到点i成为离已处理完毕的点集最近的点，但点i的距离值已经由其它处理中或处理完毕的点多次更新，所以松弛的第二个条件必须加入
                dis[edges[e.v][i].v] = dis[e.v] + edges[e.v][i].w;
                pq.push(edge(edges[e.v][i].v, dis[edges[e.v][i].v]));
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin >> t >> c >> ts;
    for (int i = 1; i <= c; i++) {
        int rs, re, ci;
        cin >> rs >> re >> ci;
        edges[rs].push_back(edge(re, ci));
    }
    memset(dis, 0x7f, sizeof(dis));
    //SPFA();
    dijkstra();
    for(int i=1;i<=t;i++)cout << dis[i]<<" ";
}

20190524更新，又写了一次Dijkstra ^v^

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<string>
#include<queue>
#include<cstring>
#include<iomanip>
using namespace std;
int n, m, s;
struct edge {
    int g, w;
    edge(int g, int w) :g(g), w(w) {}
    bool operator < (const edge& e1) const{
        return this->w > e1.w;
    }
};
vector<edge> edges[100005];
int dis[100005];
bool visited[100005];
void dijkstra() {
    memset(dis, 0x7f, sizeof(dis));
    priority_queue<edge> pq;
    pq.push(edge(s, 0));
    while (!pq.empty()) {
        edge node = pq.top();
        pq.pop();
        if (visited[node.g])continue;
        visited[node.g] = true;
        if (node.w >= dis[node.g])continue;
        dis[node.g] = node.w;
        for (int i = 0; i < edges[node.g].size(); i++) {
            edge & curE = edges[node.g][i];
            if(!visited[curE.g])pq.push(edge(curE.g, node.w + curE.w));
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++) {
        int f, g, w;
        cin >> f >> g >> w;
        edges[f].push_back(edge(g, w));
    }
    dijkstra();
    for (int i = 1; i <= n; i++) {
        if (dis[i] == 0x7f7f7f7f)cout << "2147483647 ";
        else cout << dis[i] << " ";
    }
}

洛谷 P1339 [USACO09OCT]热浪Heat Wave

发表评论

头一次用dijkstra写题也是想试验一下，priority_queue的小根堆用的不熟。。让人不知所以。。。
应该有个这样的小窍门。pq的默认是搞大根堆的，直接想非常不好想，写排序规则的地方只写<号，然后写成“假设你就要把大数排在前面，即顺着pq排序规则走的规则，然后把符号一反即可”。 两种方法代码里都有： 注意！该题中的Dijkstra算法错误，请勿继续使用！错误问题在堆判断dis时不能做到实时动态更新，而将dis插入到堆排序的结构体中可以使得堆中重复插入点相同，路径值不同的结构体值，这样点同路径值小的可以传到堆顶，大的在到顶时被忽略。
没问题的版本参见：https://renjikai.com/luogu-p4779/

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int t, c, ts, te;
struct edge {
    int v, w;
    edge(int vv, int ww) { v = vv; w = ww; }
};
vector<edge> edges[2505];
int dis[2505];
bool inqueue[2505];
//bool visited[2505];
/*
struct cmp {
    bool operator () (int i1, int i2) {
        return dis[i1] > dis[i2];
    }
};
*/
void SPFA() {
    queue<int> q;
    dis[ts] = 0;
    inqueue[ts] = true;
    q.push(ts);
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        inqueue[node] = false;
        for (int i = 0; i < edges[node].size(); i++) {
            if (dis[edges[node][i].v] > dis[node] + edges[node][i].w) {
                dis[edges[node][i].v] = dis[node] + edges[node][i].w;
                if (!inqueue[edges[node][i].v])q.push(edges[node][i].v);
            }
        }
    }
}
/*
void dijkstra() {
    priority_queue<int,vector<int>,cmp> pq;
    dis[ts] = 0;
    pq.push(ts);
    while (!pq.empty()) {
        int node = pq.top();
        pq.pop();
        if (visited[node])continue;
        visited[node] = true;
        for (int i = 0; i < edges[node].size(); i++) {
            if (!visited[edges[node][i].v] && dis[edges[node][i].v] > dis[node] + edges[node][i].w) {
                //有可能存在一种情况：虽然没有轮到点i成为离已处理完毕的点集最近的点，但点i的距离值已经由其它处理中或处理完毕的点多次更新，所以松弛的第二个条件必须加入，这也是为什么cmp必须要用实时的数据
                dis[edges[node][i].v] = dis[node] + edges[node][i].w;
                pq.push(edges[node][i].v);
            }
        }
    }
}
*/
int main() {
    ios::sync_with_stdio(false);
    cin >> t >> c >> ts >> te;
    for (int i = 1; i <= c; i++) {
        int rs, re, ci;
        cin >> rs >> re >> ci;
        edges[rs].push_back(edge(re, ci));
        edges[re].push_back(edge(rs, ci));
    }
    memset(dis, 0x7f, sizeof(dis));
    SPFA();
    //dijkstra();
    cout << dis[te];
}

洛谷 P1341 无序字母对

发表评论

本题涉及欧拉回路/欧拉路径。
参考：https://blog.csdn.net/qq_34454069/article/details/77779300
http://www.cnblogs.com/zmin/p/6947266.html
https://www.cnblogs.com/shao0099876/p/7366852.html

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<iostream>
#include<algorithm>
#include<vector>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int n;
struct e {
    char t;
    int bool_v;
    e(char t1, int v1) { t = t1; bool_v = v1; }
    bool operator < (const e& e2) const {
        return t < e2.t;
    }
};
vector<e> edge[130];
vector<char> path;
int degree[130];
bool visited[3000];
void dfs(char node) {
    for (int i = 0; i < edge[node].size(); i++) {
        if (visited[edge[node][i].bool_v])continue;
        visited[edge[node][i].bool_v] = true;
        dfs(edge[node][i].t);
    }
    path.push_back(node);
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        char c1, c2;
        cin >> c1 >> c2;
        degree[c1]++;
        degree[c2]++;
        edge[c1].push_back(e(c2, i));
        edge[c2].push_back(e(c1, i));
    }
    for (char i = 0; i <= 126; i++) {
        if (edge[i].size() > 1)sort(edge[i].begin(), edge[i].end());
    }
    int odd = 0;//奇
    char s = -1;
    for (char i = 127; i >= 0; i--) {
        if (degree[i] % 2 == 0 && degree[i] > 0) {
            if (odd == 0)s = i;
        }
        else if (degree[i] % 2 == 1) {
            odd++;
            s = i;
        }
    }
    if (!(odd == 0 || odd == 2)) {
        cout << "No Solution";
        return 0;
    }
    dfs(s);
    for (int i = path.size() - 1; i >= 0; i--) {
        cout << path[i];
    }
}

可能确实不大好理解这个代码，然后就做了一个简易的例子来说明这个问题。

洛谷 P2921 [USACO08DEC]在农场万圣节Trick or Treat on the Farm

发表评论

今后需要改良一下拓扑排序，不要一遍一遍扫。只要抓到一个入度为0的就紧追不舍即可，一遍一遍的扫很耗费时间的。。。具体可看代码。

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<iostream>
#include<algorithm>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int n;
int nxt[100005];
bool visited[100005];
int allocated[100005];
int alloc_ptr = 0;
int allocate_dis[100005];
int chainDis[100005];
int inDegree[100005];
inline void removeInDegree(int node) {
    if (inDegree[node] != 0)return;
    inDegree[node]--;
    inDegree[nxt[node]]--;
    removeInDegree(nxt[node]);
}
inline int dfsRing(int alloc, int node) {
    if (visited[node])return 0;
    visited[node] = true;
    allocated[node] = alloc;
    return 1 + dfsRing(alloc, nxt[node]);
}
inline int dfsToRing(int node) {
    if (chainDis[node] != 0)return chainDis[node];
    if (allocated[node])return chainDis[node] = allocate_dis[allocated[node]];
    else return chainDis[node] = 1 + dfsToRing(nxt[node]);
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> nxt[i];
        inDegree[nxt[i]]++;
    }
    for (int i = 1; i <= n; i++) {
        if (inDegree[i] == 0)removeInDegree(i);
    }
    for (int i = 1; i <= n; i++) {
        if (inDegree[i] <= 0 || allocated[i]) continue;
        alloc_ptr++;
        allocate_dis[alloc_ptr] = dfsRing(alloc_ptr, i);
    }
    for (int i = 1; i <= n; i++) {
        if (allocated[i])cout << allocate_dis[allocated[i]] << endl;
        else cout << dfsToRing(i) << endl;
    }
}

洛谷 P2661 信息传递

发表评论

小小的激动一下，自己做出来的。。
然后有个警醒，如果不是顺其自然简化的条件判断表达式（例如!flag，是flag==0的同义），不要生搬硬套简化，很容易出错！

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
36
37
38
39
40
#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int n;
int To[200005];
int inDegree[200005];
int getRing(int node) {
    if (!inDegree[node])return 0;
    inDegree[node] = 0;
    return 1 + getRing(To[node]);
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> To[i];
        inDegree[To[i]]++;
    }
    int flag = 0;
    do {
        flag = 0;
        for (int i = 1; i <= n; i++) {
            if (inDegree[i]==0) {
                inDegree[i]--;
                inDegree[To[i]]--;
                flag++;
            }
        }
    } while (flag!=0);
    int mmin = 0x7fffffff;
    for (int i = 1; i <= n; i++) {
        if (inDegree[i] > 0)mmin = min(mmin, getRing(i));
    }
    cout << mmin;
}

洛谷 P1108 低价购买

发表评论

头一回自己写出来个这么难的动规，小小的激动一下。。
如果直接把100分的代码贴出来，也没啥用。我把分数逐渐增长的所有代码都贴出来，万一自己以后又做到这道题没有思路可作参考。
确实很麻烦。如果直接看100分的会一头雾水，还写不出来注释，思想太复杂了。只可意会。
想看简单题解的OIer可以去洛谷题解上看。
63分：

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
36
37
#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int n;
int price[5005];
int dp[5005];
int ways[5005];
bool visited[65537];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> price[i];
    for (int i = 1; i <= n+1; i++) {
        int mDpV = 0, cWays = 1;
        for (int j = 1; j < i; j++) {
            if (price[j] > price[i]) {
                if (dp[j] > mDpV) {
                    mDpV = dp[j];
                    cWays = ways[j];
                    memset(visited, false, sizeof(visited));
                    visited[price[j]] = true;
                }
                if (dp[j] == mDpV && !visited[price[j]]) {
                    cWays += ways[j];
                    visited[price[j]] = true;
                }
            }
        }
        dp[i] = mDpV + 1;
        ways[i] = cWays;
    }
    cout << dp[n+1]-1 << " " <<ways[n+1];
}

73分：把memset的范围调小了

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
36
37
38
39
40
41
42
43
44
45
46
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int n;
int price[5005];
int dp[5005];
int ways[5005];
bool visited[65537];
int main() {
    cin >> n;
    price[0] = 65537;
    ways[0] = 1;
    int vmax = 0, vmin = 65537;
    for (int i = 1; i <= n; i++) {
        cin >> price[i];
        vmax = max(vmax, price[i]);
        vmin = min(vmin, price[i]);
    }
    for (int i = 1; i <= n+1; i++) {
        int mDpV = dp[0], cWays = 1;
        for (int j = 1; j < i; j++) {
            if (price[j] > price[i]) {
                if (dp[j] > mDpV) {
                    mDpV = dp[j];
                    cWays = ways[j];
                    memset(visited + vmin, false, sizeof(int)*(vmax - vmin + 1));
                    visited[price[j]] = true;
                }
                if (dp[j] == mDpV && !visited[price[j]]) {
                    cWays += ways[j];
                    visited[price[j]] = true;
                }
            }
        }
        dp[i] = mDpV + 1;
        ways[i] = cWays;
    }
    cout << dp[n+1]-1 << " " <<ways[n+1];
}

82分：不在每个j处都memset，而是利用版本号的想法，改为在i处更新。

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
36
37
38
39
40
41
42
43
#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int n;
int price[10000];
long long dp[10000];
long long ways[10000];
int visited[65540]; //[price][version()]
int main() {
    cin >> n;
    int vmax = 0, vmin = 65537;
    for (int i = 1; i <= n; i++) {
        cin >> price[i];
        vmax = max(vmax, price[i]);
        vmin = min(vmin, price[i]);
    }
    for (int i = 1; i <= n+1; i++) {
        long long mDpV = 0;
        long long cWays = 1;
        memset(visited, 0, sizeof(visited));
        for (int j = 1; j < i; j++) {
            if (price[j] > price[i]) {
                if (dp[j] > mDpV) {
                    mDpV = dp[j];
                    cWays = ways[j];
                    visited[price[j]] = mDpV;
                }
                if (dp[j] == mDpV && visited[price[j]]<mDpV) {
                    cWays += ways[j];
                    visited[price[j]] = mDpV;
                }
            }
        }
        dp[i] = mDpV + 1;
        ways[i] = cWays;
    }
    cout << dp[n+1]-1 << " " <<ways[n+1];
}

100分：参考别人题解发现了用后面替代前面的重要问题。

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
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int n;
int price[10000];
long long dp[10000]; //DP 数组
long long ways[10000]; //方法数 数组
long long visited[65540][2]; // [price][0]代表当前最长降序子序列长度，[price][1]代表在此情况下的方法数
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> price[i];
    for (int i = 1; i <= n+1; i++) {
        long long mDpV = 0;
        long long cWays = 1;
        memset(visited, 0, sizeof(visited));
        for (int j = 1; j < i; j++) {
            if (price[j] > price[i]) {
                //当visited[price[j]][0]有更新时，用后面的替代前面的，因为相应的方法数也会有更新
                if (dp[j] == mDpV && visited[price[j]][0]==mDpV) {
                    cWays += ways[j];
                    cWays -= visited[price[j]][1];
                    visited[price[j]][1] = ways[j];
                }
                else if (dp[j] == mDpV && visited[price[j]][0]<mDpV) {
                    cWays += ways[j];
                    visited[price[j]][0] = mDpV;
                    visited[price[j]][1] = ways[j];
                }
                else if (dp[j] > mDpV) {
                    mDpV = dp[j];
                    cWays = ways[j];
                    visited[price[j]][0] = mDpV;
                    visited[price[j]][1] = ways[j];
                }
               
            }
        }
        dp[i] = mDpV + 1;
        ways[i] = cWays;
    }
    cout << dp[n+1]-1 << " " <<ways[n+1];
}

洛谷 P1058 立体图

发表评论

虽然写的时间很长，但是AC之后随便画图可是很好玩的哦。。。

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<functional>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int m, n, am, an;
int arr[55][55];
char output[500][500];
int calM(int m, int mh, int tm) { //每行挑最大的执行一次
    return (tm - m + 1) * 2 + max(1 + 3 * mh, 1 + 2 * (m - 1));
}
inline int calN(int m, int n) { //整体执行一次
    return 1 + 4 * n + 2 * m;
}
inline void printLine(int x, int y) {
    output[x][y] = output[x][y + 4] = '+';
    output[x][y + 1] = output[x][y + 2] = output[x][y + 3] = '-';
}
inline void printRow(int x, int y) {
    output[x][y] = output[x + 2][y - 2] = '+';
    output[x + 1][y - 1] = '/';
}
inline void printHeight(int x, int y) {
    output[x][y] = output[x + 3][y] = '+';
    output[x + 1][y] = output[x + 2][y] = '|';
}
inline void printSpace(int x, int y) {
    output[x + 1][y] = output[x + 1][y + 1] = output[x + 1][y + 2] = ' ';
    output[x + 3][y - 1] = output[x + 3][y] = output[x + 3][y + 1] = ' ';
    output[x + 4][y - 1] = output[x + 4][y] = output[x + 4][y + 1] = ' ';
    output[x + 2][y + 3] = output[x + 3][y + 3] = ' ';
}
inline void printCube(int x, int y) { //左上角坐标
    printLine(x, y);
    printLine(x + 2, y - 2);
    printLine(x + 5, y - 2);
    printRow(x, y);
    printRow(x, y + 4);
    printRow(x + 3, y + 4);
    printHeight(x + 2, y - 2);
    printHeight(x + 2, y + 2);
    printHeight(x, y + 4);
    printSpace(x, y);
}
inline void printCube2(int l, int r, int h) {
    printCube(am - 3 * h - 2 * (m-l+1), 1+2 * (m - l + 1) + (r - 1) * 4);
}
inline void printAns() {
    for (int i = 1; i <= am; i++) {
        cout << output[i] + 1 << endl;
    }
    cout << endl;
}
int main() {
    cin >> m >> n;
    an = calN(m, n);
    for (int i = 1; i <= m; i++) {
        int mmax = 0;
        for (int j = 1; j <= n; j++) {
            cin >> arr[i][j];
            mmax = max(mmax, arr[i][j]);
        }
        am = max(am, calM(i, mmax, m));
    }
    for (int i = 1; i <= am; i++) {
        for (int j = 1; j <= an; j++) {
            output[i][j] = '.';
        }
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= arr[i][j]; k++) {
                printCube2(i, j, k);
                //printAns();
            }
        }
    }
    printAns();
}

提示：把79行的注释符号去掉可以看到图形生成全过程哦；
写了个好玩的小程序，随机生成数组中的高度哦。。。
各位OIer可以随便试试。。。

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<functional>
#include<ctime>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int m, n, am, an;
int arr[55][55];
char output[500][500];
int calM(int m, int mh, int tm) { //每行挑最大的执行一次
    return (tm - m + 1) * 2 + max(1 + 3 * mh, 1 + 2 * (m - 1));
}
inline int calN(int m, int n) { //整体执行一次
    return 1 + 4 * n + 2 * m;
}
inline void printLine(int x, int y) {
    output[x][y] = output[x][y + 4] = '+';
    output[x][y + 1] = output[x][y + 2] = output[x][y + 3] = '-';
}
inline void printRow(int x, int y) {
    output[x][y] = output[x + 2][y - 2] = '+';
    output[x + 1][y - 1] = '/';
}
inline void printHeight(int x, int y) {
    output[x][y] = output[x + 3][y] = '+';
    output[x + 1][y] = output[x + 2][y] = '|';
}
inline void printSpace(int x, int y) {
    output[x + 1][y] = output[x + 1][y + 1] = output[x + 1][y + 2] = ' ';
    output[x + 3][y - 1] = output[x + 3][y] = output[x + 3][y + 1] = ' ';
    output[x + 4][y - 1] = output[x + 4][y] = output[x + 4][y + 1] = ' ';
    output[x + 2][y + 3] = output[x + 3][y + 3] = ' ';
}
inline void printCube(int x, int y) { //左上角坐标
    printLine(x, y);
    printLine(x + 2, y - 2);
    printLine(x + 5, y - 2);
    printRow(x, y);
    printRow(x, y + 4);
    printRow(x + 3, y + 4);
    printHeight(x + 2, y - 2);
    printHeight(x + 2, y + 2);
    printHeight(x, y + 4);
    printSpace(x, y);
}
inline void printCube2(int l, int r, int h) {
    printCube(am - 3 * h - 2 * (m - l + 1), 1 + 2 * (m - l + 1) + (r - 1) * 4);
}
inline void printArray() {
    cout << "Printing each element of the array:" << endl;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= m; j++) {
            cout << arr[i][j] << " ";
        }
        cout << endl;
    }
}
inline void printAns() {
    for (int i = 1; i <= am; i++) {
        cout << output[i] + 1 << endl;
    }
    cout << endl;
}
int main() {
    srand((unsigned)time(NULL));
    cout << "Please input the side length "n" of the cube array (n<=50):";
    int len;
    cin >> len;
    m = n = len;
    an = calN(m, n);
    cout << "Please input the max height "mh" of cubes in each array item (1<=mh<=100):";
    int mh;
    cin >> mh;
    cout << "Do you want to show the whole process of filling?(Answer with 0[No] or 1[Yes]):";
    bool flag;
    cin >> flag;
    for (int i = 1; i <= m; i++) {
        int mmax = 0;
        for (int j = 1; j <= n; j++) {
            arr[i][j] = rand() % mh + 1;
            mmax = max(mmax, arr[i][j]);
        }
        am = max(am, calM(i, mmax, m));
    }
    for (int i = 1; i <= am; i++) {
        for (int j = 1; j <= an; j++) {
            output[i][j] = '.';
        }
    }
    cout << "Automatically generated an array,printed in the following.Press ENTER to continue." << endl;
    printArray();
    cin.get(); cin.get();
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= arr[i][j]; k++) {
                if (flag)cout << "Printing cube on postion(" << i << "," << j << "," << k << ")." << endl;
                printCube2(i, j, k);
                if (flag)printAns();
            }
        }
    }
    cout << "Printing Final Result:" << endl;
    printAns();
}

洛谷 P1541 乌龟棋

发表评论
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
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<cstring>
using namespace std;
int n,m;
int a[355],b[6];
int f[45][45][45][45];
int safeF(int i,int j,int k,int l){
    if(i<0||j<0|k<0||l<0)return 0;
    else return f[i][j][k][l];
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=m;i++){
        int t;
        cin>>t;
        b[t]++;
    }
    for(int i=0;i<=b[1];i++)for(int j=0;j<=b[2];j++)for(int k=0;k<=b[3];k++)for(int l=0;l<=b[4];l++){
        f[i][j][k][l]=max(max(safeF(i-1,j,k,l),safeF(i,j-1,k,l)),max(safeF(i,j,k-1,l),safeF(i,j,k,l-1)))+a[i+2*j+3*k+4*l+1];
    }
    cout<<f[b[1]][b[2]][b[3]][b[4]];
}

洛谷 P1880 [NOI1995]石子合并

发表评论

转移方程是看别人的……
参考：易懂https://www.luogu.org/blog/user45556/solution-p1880
区间动规经典题目？

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
36
37
38
39
40
41
42
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int arr[205];
int presum[205];
int fMax[205][205], fMin[205][205];
int dfsMax(int l, int r) {
    if (l == r)return 0;
    if (fMax[l][r] != 0)return fMax[l][r];
    int dIJ = presum[r] - presum[l - 1];
    int mmax = 0;
    for (int k = l; k < r; k++) mmax = max(mmax, dfsMax(l, k) + dfsMax(k + 1, r) + dIJ);
    return fMax[l][r] = mmax;
}
int dfsMin(int l, int r) {
    if (l == r)return 0;
    if (fMin[l][r] != 0)return fMin[l][r];
    int dIJ = presum[r] - presum[l - 1];
    int mmin = 0x7fffffff;
    for (int k = l; k < r; k++)mmin = min(mmin, dfsMin(l, k) + dfsMin(k + 1, r) + dIJ);
    return fMin[l][r] = mmin;
}
int main(){
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> arr[i];
    for (int i = n + 1; i <= 2*n; i++)arr[i] = arr[i - n];
    for (int i = 1; i <= 2 * n; i++)presum[i] = presum[i - 1] + arr[i];
    int mmin = 0x7fffffff;
    for (int i = 1; i <= n; i++) {
        mmin = min(mmin, dfsMin(i, i + n - 1));
    }
    cout << mmin << endl;
    int mmax = 0;
    for (int i = 1; i <= n; i++) {
        mmax = max(mmax, dfsMax(i, i + n - 1));
    }
    cout << mmax << endl;

}