日度归档：6 8 月, 2018

洛谷 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];
}