链表

单向链表acwing826

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
#include<iostream>

using namespace std;

// 增删改查
const int N = 1e5 + 10;
int head, idx, e[N], ne[N];

void init(){
    head = -1;
    idx = 0;
}

void add_to_head(int x){
    e[idx] = x, ne[idx] = head;
    head = idx;
    idx++;
}

void add(int k, int x){
    e[idx] = x, ne[idx] = ne[k];
    ne[k] = idx;
    idx++;
}

void remove(int k){
    ne[k] = ne[ne[k]];
}

void print(){
    for(int i = head; i != -1; i = ne[i]){
        cout << e[i] << " ";
    }
    cout << endl;
}

int main(){
    init();
    int m;
    char a;
    int b,c;
    cin >> m;
    for(int i=0;i<m;i++){
        cin >> a;
        if (a=='H'){
            cin >> b;
            add_to_head(b);
        }else if(a=='D'){
            cin >> b;
            if(!b) head = ne[head];
            else remove(b-1);
        }else{
            cin >> b >> c;
            add(b-1,c);
        }
        // switch(a){
        //     case('H'):
        //         cin >> b;
        //         add_to_head(b);
        //         break;
        //     case('D'):
        //         cin >> b;
        //         remove(b-1);
        //         break;
        //     case('I'):
        //         cin >> b >> c;
        //         add(b-1,c);
        //         break;
        // }
    }
    print();
}

双向链表acwing827

这代码写的太美了acwing827 

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
#include<iostream>
#include<string>

using namespace std;

// 增删改查
const int N = 1e5 + 10;
int idx, e[N], l[N], r[N];

void init(){
    // 这里0就是头节点，1就是尾节点
    r[0] = 1; l[1] = 0;
    idx = 2;
}


void add(int k, int x){ // 在第k个元素后插入x
    e[idx] = x; l[idx] = k; r[idx] = r[k];
    l[r[k]] = idx; r[k] = idx;
    idx++;
}

void remove(int k){ // 删除第k个元素
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

int main(){
    init();
    string op;
    int k, x, m;
    cin >> m;
    for (int i = 0; i < m; i++){
        cin >> op;
        if(op == "L"){
            cin >> x;
            // 在最左侧插入，即在头节点0的右边插入
            add(0, x);
        }else if(op == "R"){
            // 在最右侧插入，即在尾节点1的左边插入，即在尾节点1的左边节点l[1]的右边插入
            cin >> x;
            add(l[1], x);
        }else if(op == "IL"){
            cin >> k >> x;
            add(l[k+1], x);
        }else if(op == "IR"){
            cin >> k >> x;
            add(k+1, x);
        }else{
            cin >> k;
            remove(k+1);
        }
    }
    
    for(int i=r[0];i!=1;i=r[i]) cout<<e[i]<<' ';
    cout << endl;
}

0-1背包

acwing 讲的很好 用集合来理解

不化为一维可以使用2维的滚动数组，理解起来更加简单。
一行存旧值，一行赋新值。 

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
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010;
int n,m;
int v[N], w[N];
int f[N][N];
// 化二维为1维
int f2[N];

int main(){
    // 求的是背包最大价值
    cin >> n>> m;
    for(int i=1;i<=n;i++) cin>> v[i] >> w[i];

    for(int i=1;i<=n;i++)
    for (int j = 1;j<=m;j++){
        f[i][j] = f[i-1][j];
        if (v[i]<=j) f[i][j] = max(f[i][j], f[i-1][j-v[i]]+w[i]);
    }


    // 因为二维数组的更新只用到了上一层，所以为什么不直接用1维数组？
    // 这个一维数组怎么更新？
    // 若当前背包大小不能放下vi，数值保持不变（这里的当前背包大小就是j）
    // 若当前背包大小能放下vi，则需要判断加入vi的后价值是否比不加大
    // 怎么判断？利用f[i-1][j-v[i]]+w[i]，即为f[j-v[i]]+w[i]
    // 我们这里是一维数组，需要的是f[j-v[i]]未更新的值
    // j从小到大可能f[j-v[i]]变了，被更新了，vi可能在里面了
    // 从大大小就不会出现这种情况，因为我们使用的值是前面的而不是后面的，所以不会影响
    for(int i=1;i<=n;i++)
    for (int j = m;j>=v[i];j--){
        f2[j] = max(f2[j], f2[j-v[i]]+w[i]);
    }
    cout << f[n][m] << ' '<<f2[m]<<endl;

    // for(int i=1;i<=n;i++){
    //     for (int j = 1;j<=m;j++)
    //     cout << f[i][j] << ' ';
    //     cout << endl;
    // }
}

完全背包

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
//朴素写法
// 从1出发是因为0行0列为0
// 提交直接time limit
for(int i=1;i<=n;i++){
    for(int j =1;j<=m;j++){
        for(int k=0;v[i]*k<=j;k++){
            f[i][j] = max(f[i][j], f[i-1][j-k*v[i]]+k*w[i]);
        }
    }
}

// 从数学方面优化
// f[i][j] = max{f[i-1][j]（也可以表示为f[i-1][j-0*vi]+0*wi), f[i-1][j-1*vi]+1*wi,...,f[i-1][j-k*vi]+k*wi}
// 而f[i][j-vi] = max{f[i-1][j-vi], f[i-1][j-2vi]+wi,...,f[i-1][j-kvi]+(k-1)wi}
// 找关系
for(int i=1;i<=n;i++){
    for(int j =1;j<=m;j++){
        f[i][j] = f[i-1][j];
        if (j>=v[i])
            f[i][j] = max(f[i][j], f[i][j-v[i]]+w[i]);
    }
}
// 优化二维数组
for(int i=1;i<=n;i++){
    for(int j =v[i];j<=m;j++){
        f[j] = max(f[j], f[j-v[i]]+w[i]);
    }
}
cout << f[n][m] << endl;

注意为什么01与完全的j的遍历顺序为什么不同。

多重背包问题

二进制优化

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
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010;
int n,m;
int v[N], w[N];
int f[N];


// 多重背包问题通过二进制拆分转化为01背包问题
int main(){
    // 求的是背包最大价值
    int cnt = 0;
    cin >> n>> m;
    for(int i=1;i<=n;i++){
        int vi,wi,ci;
        cin >> vi >> wi >> ci;
        int k = 1;
        while(k<=ci){
            cnt++;
            v[cnt] = vi*k;
            w[cnt] = wi*k;
            ci-=k;
            k = k*2;
        }
        if(ci>0){
            cnt++;
            v[cnt] = vi*ci;
            w[cnt] = wi*ci;
        }
    }
    for(int i=1;i<=cnt;i++){
        for(int j=m;j>=v[i];j--){
            f[j] = max(f[j], f[j-v[i]]+w[i]);
        }
    }

    cout << f[m] << endl;
}

多重背包问题

朴素

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
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 110;
int v[N][N], w[N][N], s[N];
int f[N][N];
int n, m; //组数， 背包大小

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin >> s[i];
        for(int j=1;j<=s[i];j++){
            cin >> v[i][j] >> w[i][j];
        }
    }

    //dp
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            f[i][j] = f[i-1][j];
            for(int k=1;k<=s[i];k++){
                if(v[i][k]<=j) 
                f[i][j] = max(f[i][j], f[i-1][j-v[i][k]]+w[i][k]);
            }
        }
    }
    cout << f[n][m] << endl;
}

优化f

1
2
3
4
5
6
7
8
9
for(int i=1;i<=n;i++){
    for(int j=m;j>=1;j--){
        // 这里可以加个复杂的判断，判断j与min(v[i])的大小关系，可以减少循环
        for(int k=1;k<=s[i];k++){
            if(v[i][k]<=j) 
            f[j] = max(f[j], f[j-v[i][k]]+w[i][k]);
        }
    }
}