ACM►图论

UVA10129-Play on Words（欧拉道路）

题目链接：

UVA10129-Play on Words

题目大意：

给出一些单词，如果一个单词的首部字母和另一个单词的尾部字母相同，则可以首尾连接，每个单词只能使用一次，判断这些字母是否可以全部连接成一个串。

解题过程：

  • 刚开始没弄清有向图和无向图欧拉路的定义，以为只判断边就可以了，于是简单写了一个只判读边的。

  • 显然是错误的，自己试了几组数据就不对。
    我这样想可能是被这个题带偏了节奏（误

  • 然后仔细看了下书上的定义，还要保证图必须是连同的才可以，于是写了下，一发AC。

题目分析：

  • 首先明确欧拉路的充要条件：
  • 对于无向图，最多只有两个点的度为1，则一定存在欧拉回路。
  • 对于有向图，最多只能有两个点的入度不等于出度，而且一个是入度恰好比出度大1，另一个是出度比入度大1。
  • 以上两个图都要保证底图（忽略边的方向后得到的图）是连通的。
  • 如果一个图不存在奇点（度数为奇数的点）则构成欧拉回路，否则为欧拉路。
  • 题目是有向图，把每个字母当做点，用两个数组统计每个点入度和出度，并判断。
  • 用dfs的方法把图遍历一遍，看是否每个点都到达过，是的话则是连通的图。
  • 两个判断条件与运算即是结果。

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

int head[26], tail[26], data[26][26], mark[26];

bool dfs(int k)
{
    mark[k] = 0;
    for (int i = 0; i < 26; i++)
    {
        if (data[k][i])
        {
            data[k][i] = 0;
            data[i][k] = 0;
            dfs(i);
        }
    }
}

bool judge()
{
    int k;
    for (int i = 0; i < 26; i++)
    {
        if (mark[i] != 0)
        {
            k = i;
            break;
        }
    }
    dfs(k);
    for (int i = 0; i < 26; i++)
        if (mark[i])
            return false;
    return true;
}

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        memset(head, 0, sizeof(head));
        memset(tail, 0, sizeof(tail));
        memset(data, 0, sizeof(data));
        memset(mark, 0, sizeof(mark));
        int n, flag = 1;
        cin >> n;
        string str;
        while (n--)
        {
            cin >> str;
            head[str[0]-'a']++;
            tail[str[str.size()-1]-'a']++;

            data[str[0]-'a'][str[str.size()-1]-'a'] = 1;
            data[str[str.size()-1]-'a'][str[0]-'a'] = 1;

            mark[str[0]-'a'] = 1;
            mark[str[str.size()-1]-'a'] = 1;
        }
        int a = 0, b = 0;
        for (int i = 0; i < 26; i++)
        {
            if (head[i]-tail[i] == 1)
                a++;
            if (tail[i]-head[i] == 1)
                b++;
            if (abs(head[i]-tail[i]) > 1)
                flag = 0;
        }
        if (flag && a == b && a <= 1 && judge())
            cout << "Ordering is possible." << endl;
        else
            cout << "The door cannot be opened." << 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <cstring>
#include <stack>
using namespace std;

const int MAX = 1123;

int m, n;
int data[MAX][MAX];
stack<int> ans;

void dfs(int pos)
{
    for (int i = 1; i <= n; i++)
    {
        if (data[pos][i])
        {
            data[pos][i] = 0;
            data[i][pos] = 0;
            dfs(i);
        }
    }
    ans.push(pos);
}

void put()
{
    while (!ans.empty())
    {
        cout << "->" << ans.top();
        ans.pop();
    }
    cout << endl;
}

int main()
{
    while (cin >> n >> m)
    {
        memset(data, 0, sizeof(data));
        int a, b;
        for (int i = 0; i < m; i++)
        {
            cin >> a >> b;
            data[a][b] = 1;
            data[b][a] = 1;
        }
        dfs(1);
        put();
    }
}
游戏

2048（游戏）

玩法：

即模仿市场上的2048游戏。

效果图：

这里写图片描述
这里写图片描述
这里写图片描述

实现原理：

  • 就当是一个非常复杂的模拟题，整理好思路，搭好大体结构不难写。
  • 重点是如何判断方块是否合并那里，还有检测是否游戏结束。
  • 分数用一个全局变量储存，每次更新出性方块时加分。
  • 为方块分数加了个等比例增加的#号，要不玩起来难受的要死。
    -

源代码：

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
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
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include<conio.h>

int a[4][4], SCORE = 0, prt;

int num()
{
    return rand()%4;
}

int scan()
{
    int i, j, t = 0;
    for(i = 0; i < 4; i++)
    {
        for(j = 0; j < 4; j++)
        {
            if (a[i][j] == 0)
            {
                return 1;
            }
        }

    }
    return 0;
}

void crt()
{
    SCORE += 2;
    int i,j;
    for(;1;)
    {
        i = num();
        j = num();
        printf("%d %d", i, j);
        if (a[i][j] == 0)
        {
            a[i][j] = 2;
            break;
        }
    }
}

void frmt()
{
    int i, d;
    for (i = 0; i < 4; i++)
    {
        for (d = 0; d < 4; d++)
        {
            a[i][d] = 0;
        }
    }
}

void put()
{
    int i,d;
    printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\t\t\tScode: \t%d\n\n\t\t\t┌──────┬──────┬──────┬──────┐\n\t\t\t", SCORE);
    for (i = 0; i < 4; i++)
    {

        for (d = 0; d < 4; d++)
        {
            if (a[i][d] == 2048)
                printf("│##########%d ", a[i][d]);
            else if (a[i][d] == 1024)
                printf("│#########%2d ", a[i][d]);
            else if (a[i][d] == 512)
                printf("│########%3d ", a[i][d]);
            else if (a[i][d] == 256)
                printf("│#######%4d ", a[i][d]);
            else if (a[i][d] == 128)
                printf("│######%5d ", a[i][d]);
            else if (a[i][d] == 64)
                printf("│#####%6d ", a[i][d]);
            else if (a[i][d] == 32)
                printf("│####%7d ", a[i][d]);
            else if (a[i][d] == 16)
                printf("│###%8d ", a[i][d]);
            else if (a[i][d] == 8)
                printf("│##%9d ", a[i][d]);
            else if (a[i][d] == 4)
                printf("│#%10d ", a[i][d]);
            else if (a[i][d] == 2)
                printf("│%11d ", a[i][d]);
            else
            printf("│            ", a[i][d]);
        }
        printf("│");

        if (i != 3)
        {
            printf("\n\t\t\t├──────┼──────┼──────┼──────┤\n\t\t\t");
        }
    }
    printf("\n\t\t\t└──────┴──────┴──────┴──────┘\n\n\n");
}


void A_()
{
    int i, j, t;
    for (i = 0; i < 4; i++)
    {
        for (j = 0; j < 4; j++)
        {
            if (a[i][j] == 0)
                continue;
            else
            {
                for (t = j + 1; t < 4; t++)
                {
                    if (t != 0 && a[i][t] == a[i][j])
                    {
                        prt=1;
                        a[i][j] *= 2;
                        a[i][t] = 0;
                    }
                    else if (t != 0 && a[i][t] != a[i][j])
                        break;
                }
            }
        }
    }

    for (i = 0; i < 4; i++)
    {
        for (j = 0; j < 4; j++)
        {
            if (a[i][j] == 0)
            {
                for (t = j + 1; t < 4; t++)
                {
                    if (a[i][t] != 0)
                    {
                        prt=1;
                        a[i][j] = a[i][t];
                        a[i][t] = 0;
                        break;
                    }
                }
            }
        }
    }
}

void D_()
{
    int i, j, t;
    for (i = 0; i < 4; i++)
    {
        for (j = 3; j >= 0; j--)
        {
            if (a[i][j] == 0)
                continue;
            else
            {
                for (t = j - 1; t >= 0; t--)
                {
                    if (t != 0 && a[i][t] == a[i][j])
                    {
                        prt=1;
                        a[i][j] *= 2;
                        a[i][t] = 0;
                    }
                    else if (t != 0 && a[i][t] != a[i][j])
                        break;
                }
            }
        }
    }

    for (i = 0; i < 4; i++)
    {
        for (j = 3; j >= 0; j--)
        {
            if (a[i][j] == 0)
            {
                for (t = j - 1; t >= 0; t--)
                {
                    if (a[i][t] != 0)
                    {
                        prt=1;
                        a[i][j] = a[i][t];
                        a[i][t] = 0;
                        break;
                    }
                }
            }
        }
    }
}

void S_()
{
    int i, j, t;
    for (i = 0; i < 4; i++)
    {
        for (j = 3; j >= 0; j--)
        {
            if (a[j][i] == 0)
                continue;
            else
            {
                for (t = j - 1; t >= 0; t--)
                {
                    if (t != 0 && a[j][i] == a[t][i])
                    {
                        prt=1;
                        a[j][i] *= 2;
                        a[t][i] = 0;
                    }
                    else if (t != 0 && a[t][i] != a[j][i])
                        break;
                }
            }
        }
    }

    for (i = 0; i < 4; i++)
    {
        for (j = 3; j >= 0; j--)
        {
            if (a[j][i] == 0)
            {
                for (t = j - 1; t >= 0; t--)
                {
                    if (a[t][i] != 0)
                    {
                        prt=1;
                        a[j][i] = a[t][i];
                        a[t][i] = 0;
                        break;
                    }
                }
            }
        }
    }
}

void W_()
{
    int i, j, t;
    for (i = 0; i < 4; i++)
    {
        for (j = 0; j < 4; j++)
        {
            if (a[j][i] == 0)
                continue;
            else
            {
                for (t = j + 1; t < 4; t++)
                {
                    if (t != 0 && a[j][i] == a[t][i])
                    {
                        prt=1;
                        a[j][i] *= 2;
                        a[t][i] = 0;
                    }
                    else if (t != 0 && a[t][i] != a[j][i])
                        break;
                }
            }
        }
    }

    for (i = 0; i < 4; i++)
    {
        for (j = 0; j < 4; j++)
        {
            if (a[j][i] == 0)
            {
                for (t = j + 1; t < 4; t++)
                {
                    if (a[t][i] != 0)
                    {
                        prt=1;
                        a[j][i] = a[t][i];
                        a[t][i] = 0;
                        break;
                    }
                }
            }
        }
    }
}

int main()
{
    int judge;
    char ch;
    srand((unsigned) time(NULL));

    printf("\n\n\n\n\n\n\t\t\tW S A D Control direction\n\n\n\n\t\t\tPress any key to start the game...\n");
    getch();

    frmt();
    crt();
    put();

    for (;1;)
    {
        prt = 0;
        for (;1;)
        {
            printf("\n\n\n\n\n\n\n\nPlease enter: ");
            ch = getch();
            putchar(ch);
            if(ch >= 'a' && ch <= 'z')
                ch -= 32;
            if(ch == 'W' || ch == 'A' || ch == 'D' || ch == 'S')
                break;
        }

        if (ch == 'A')
            A_();

        if (ch == 'D')
            D_();

        if (ch == 'S')
            S_();

        if (ch == 'W')
            W_();

        if (scan())
        {
            if (prt)
                crt();
            put();
        }
        else
        {
            printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\t\t\t\tGame Over\n\n\n\n\n\n\n\n\n\n\n\n\n\n");
            break;
        }
    }
    getchar();
}

PS：

印象中好像是十月一刚开学时，非常无聊写的，当作是锻炼代码能力了，也是图个好玩，成就感也是有的，毕竟是第一个有点可玩性的游戏，有时候真的停不下来233。

ACM►搜索

自动走迷宫（DFS）

功能：

  • 输入一张地图，找出一条可到达终点的路径，1代表不可走，0代表可走，2代表终点。

效果图：

这里写图片描述这里写图片描述

实现原理：

  • DFS遍历。
  • 二维数组储存地图。

源代码：

因为输入数据太麻烦，附了组数据。

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
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
#include<stdio.h>
typedef struct
{
    int x;
    int y;
    int s;
    int f;
}note;

int map[999][999], book[999][999];
note queue[999];

int main()
{
    int n, i, j, head, tail, x, y, tx, ty, flag;
    int drct[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

    scanf("%d", &n);

    head = 1;
    tail = 1;

    x = 1;
    y = 1;
    //scanf("%d %d", &x, &y);

    queue[tail].x = x;
    queue[tail].y = y;
    queue[tail].s = 0;
    tail++;

    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= n; j++)
        {
            scanf("%d", &map[i][j]);
        }
    }




    while (head < tail)
    {
        for (i = 0; i < 4; i++)
        {
            tx = queue[head].x + drct[i][0];
            ty = queue[head].y + drct[i][1];

            if (tx < 1 || tx > n || ty < 1 || ty > n)
            {
                continue;
            }

            if (map[tx][ty] == 0 && book[tx][ty] == 0)
            {
                book[tx][ty] = 1;

                queue[tail].x = tx;
                queue[tail].y = ty;
                queue[tail].f = head;
                queue[tail].s = queue[head].s + 1;
                //printf("###%d %d\n", tail, queue[tail].f);
                tail++;
            }

            //printf("###%d %d %d %d %d %d\n", tail, queue[tail-1].f, queue[tail - 1].x, queue[tail - 1].y, tx, ty);

            if (map[tx][ty] == 2)
            {
                flag = 1;
                break;
            }
        }

        if (flag == 1)
        {
            break;
        }
        head++;
    }

    if (flag == 1)
    {

    map[tx][ty] = 3;
    for (;;)
    {
        map[queue[head].x][queue[head].y] = 3;
        //printf("%d %d  %d\n", queue[head].x, queue[head].y, i);//
        if(head == 1)
            break;
        head = queue[head].f;
        //getchar();

    }

    putchar('\n');

    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= n; j++)
        {
            if (map[i][j] == 3)
                printf("! ");
            else if (map[i][j] == 1)
                printf("# ");
            else
                printf("* ");
        }
        putchar('\n');
    }

    }

    else
        printf("NO\n");




}

/*
20
0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0
0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0
0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0
0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0
1 0 1 1 0 1 0 1 1 1 1 0 1 1 0 1 0 1 1 1
0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0
0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0
0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 1 1 0 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1
0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0
0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0
0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 1 1 0 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1
0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0
0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0
0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
1 0 1 1 1 1 0 1 1 0 1 0 1 1 1 1 0 1 1 2
*/

PS:

当时刚从啊哈算法上看到DFS，还没实现过，第一次实现写的这东西，也是感兴趣，成就感满满！

ACM►搜索

数独问题（工具）

功能：

  • 输入一个数独（用二维数组表示），求出数独的解。

效果图：

这里写图片描述这里写图片描述

实现原理：

  • DFS搜索遍历。
  • 二维数组储存数据。

源代码：

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
#include<iostream>
#include<cstring>
#include<cstring>
#include<cstdio>
using namespace std;

int data[112][112];

void put()
{
    cout << "----------------------" << endl;
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            cout << data[i][j] << " ";
            if ((j+1)%3 == 0)
                cout << " ";
        }
        cout << endl;
        if ((i+1)%3 == 0)
            cout << endl;
    }
    cout << "----------------------" << endl;
}


bool check(int x, int y)
{
    for (int i = 0; i <= 9; i++)
    {
        if (data[i][y] == data[x][y] && i != x)
            return false;
        if (data[x][i] == data[x][y] && i != y)
            return false;
    }

    int x0 = x/3*3;
    int y0 = y/3*3;

    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            if (i+x0 == x && j+y0 == y)
                continue;
            if (data[i+x0][j+y0] == data[x][y])
                return false;
        }
    }

    return true;
}

int fun(int cnt)
{
    int x, y;
    if (cnt == 81)
        return 1;

    x = cnt/9;
    y = cnt%9;


    if (data[x][y] != 0)
    {
        fun(cnt+1);
    }
    else
    {
        for (int i = 1; i <= 9; i++)
        {
            data[x][y] = i;
            if (check(x, y))
            {
                if(fun(cnt+1))
                    return 1;
            }
        }
        data[x][y] = 0;
        return 0;
    }
}

int main()
{
    int n, x, y, t;
    while (cin >> n)
    {
        memset(data, 0, sizeof(data));
        for (int i = 0; i < n; i++)
        {
            cin >> x >> y >> t;
            data[x-1][y-1] = t;
        }
        fun(0);
        cout << "end" << endl;
        put();
    }
}

PS：

当初群里有人问一个数独怎么解时，然后自己DFS也不太熟练，花了半个小时写了这个，满满的成就感！

ACM►DP

HDOJ1176. 免费馅饼.（DP）

题目链接：

免费馅饼

题目大意：

这里写图片描述
初始位置为5，输入时间和位置，从1秒开始，每次可以移动一个位置，一秒时可接住4,5,6处馅饼，求最大接住馅饼数。

解题过程：

  • 刚开始就找到了状态转移方程：

  • j代表位置，i代表时间
    dp[j][i] = max(dp[j-1][i], dp[j-1][i-1], dp[j-1][i+1]) + data[j][i]; （j点位置曾经达到过）

  • 数塔是没想到，看到题解后才发现原来这可以归一类问题

  • 不过没想到状态转移方程出来后题目还是WA，莫名其妙，反复改后变成TLE了，介于这题cin都会TLE估计是卡了常数……
  • 于是发现别人数塔都是从后往前数的于是改了下状态转移方程A了，这样也不需要开data数组了。
  • 于是找了下之前数塔的题，发现直接都是从前往后数的，或者多开了一个数组……算是学到了。

题目分析：

  • 就是一个数塔
  • j代表位置，i代表时间
  • 状态转移方程：
    dp[j][i] = max(dp[j][i+1], dp[j-1][i+1], dp[j+1][i+1]) + dp[j][i]

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
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

int dp[20][1123456];

int MaxOf3(int a, int b, int c){
    int max = (a > b) ? a : b;
    return (max > c) ? max : c;
}

int MaxOf2(int a, int b){
    return (a > b) ? a : b;
}

int main()
{
    int n;
    while ((scanf("%d", &n) != EOF) && n)
    {
        int maxt = 0, position, time;

        memset(dp, 0, sizeof(dp));

        for (int i = 0; i < n; i++)
        {
            scanf("%d %d", &position, &time);
            dp[position+1][time]++;
            if (maxt < time)
                maxt = time;
        }

        for (int i = maxt; i >= 0; i--)
        {
            for (int j = 1; j < 12; j++)
            {
                dp[j][i] = MaxOf3(dp[j][i+1], dp[j-1][i+1], dp[j+1][i+1]) + dp[j][i];
            }
        }

        cout << dp[6][0] << endl;
    }
}

从前往后TLE的错误代码：

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
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

int dp[20][1123456];
int data[20][1123456];

int MaxOf3(int a, int b, int c){
    int max = (a > b) ? a : b;
    return (max > c) ? max : c;
}

int MaxOf2(int a, int b){
    return (a > b) ? a : b;
}

int main()
{
    int n;
    while ((scanf("%d", &n) != EOF) && n)
    {
        int maxt = 0, position, time;

        memset(dp, -1, sizeof(dp));
        memset(data, 0, sizeof(data));
        dp[6][0] = 0;

        for (int i = 0; i < n; i++)
        {
            scanf("%d %d", &position, &time);
            data[position+1][time]++;
            if (maxt < time)
                maxt = time;
        }


        for (int i = 1; i <= maxt; i++)
        {
            for (int j = 1; j < 12; j++)
            {
                dp[j][i] = MaxOf3(dp[j][i-1], dp[j-1][i-1], dp[j+1][i-1]);
                if (dp[j][i] != -1)
                    dp[j][i] += data[j][i];
            }
        }

        int ans = -1;
        for (int i = 0; i < 12; i++)
        {
            if (ans < dp[i][maxt])
                ans = dp[i][maxt];
        }
        cout << ans << endl;
    }
}
ACM►DP

CodeForces 255C. Almost Arithmetical Progression (DP)

题目链接：

CodeForces255C.

题目大意：

看起来题目给的公式很复杂，其实就是找最长的 1,2,1,2 类似这样的最长子序列.
数据小于4000.

解题过程：

  • 看到这个题首先就想到了用DP来做，毕竟正在刷DP的专题，刚开始想着这个题类似最长公共子序列那样，然后想了一个多小时也没结果，最后比赛快结束的半小时想起来这个和最长上升子序列有点像（后来发现也不是）。

  • 比赛完后想到了一个状态转移方程（错误的）用两个一维数组，一个用来记录以每一个数为最后一个数的最大长度，另一个储存最大长度的情况下的上一个数。
    错误的状态转移方程： a[i] = a[j] + 1 (a[i] == b[i])
    显然是错误的，于是我还考虑了下最长有多种情况的情况，用set储存上一个数，还是错误（毕竟想法就不太对）。

  • 于是隔了一天还是没想起来，于是百度了下题解，找到了一个不错的博客：题解
    可以看出来这篇博客风格也照抄了一下233，分析的很清楚，然后自己拿纸模拟了一遍，感觉这么简单的题怎么没想出来……

分析过程：

  • 用a[i][j]二维数组储存状态，i代表以第几个数结束，j代表倒数第二个数。
  • 状态转移方程：dp[i][j] = dp[j][k] + 1 (a[k]==a[i])
  • 看巨巨的题解K在状态转移的过程中就可以找到了。

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
#include <iostream>
#define MAX 4123
using namespace std;

int data[MAX];
int dp[MAX][MAX];

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> data[i];
    }

    int ans = 1;
    for (int i = 1; i <= n; i++)
    {
        int k = -1;
        for (int j = 1; j < i; j++)
        {
            if (k == -1)
                dp[i][j] = 2;
            else
                dp[i][j] = dp[j][k] + 1;
            if (data[i] == data[j])
                k = j;
            if (ans < dp[i][j])
                ans = dp[i][j];
        }
    }
    cout << ans;
}

暴力遍历代码：

看题解之前想碰碰运气写的暴力代码，时间复杂度O(n^3)，当然TLE啦……

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

set<int> check;
vector<int> store;
int data[41234];
int n;

int scan(int a, int b)
{
    int judge = 0;
    int sum = 0;
    for (int i = 0; i < n; i++)
    {
        if (judge == 0 && (data[i] == a || data[i] == b) || data[i] == judge)
        {
            if (data[i] == a)
            {
                judge = b;
            }
            if (data[i] == b)
            {
                judge = a;
            }
            sum++;
        }
    }
    return sum;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> data[i];
        if (check.count(data[i]) == 0)
        {
            check.insert(data[i]);
            store.push_back(data[i]);
        }
    }
    int ans = 0;
    for (int i = 0; i < store.size(); i++)
    {
        for (int j = i; j < store.size(); j++)
        {
            int t = scan(data[i], data[j]);
            ans = ans > t? ans:t;
        }
    }
    cout << ans;
}
ACM►DP

SDUTOJ. LCS问题.(DP)

题目链接：

CodeForces255C.

题目大意：

看起来题目给的公式很复杂，其实就是找最长的 1,2,1,2 类似这样的最长子序列.
数据小于4000.

解题过程：

  • 看到这个题首先就想到了用DP来做，毕竟正在刷DP的专题，刚开始想着这个题类似最长公共子序列那样，然后想了一个多小时也没结果，最后比赛快结束的半小时想起来这个和最长上升子序列有点像（后来发现也不是）。

  • 比赛完后想到了一个状态转移方程（错误的）用两个一维数组，一个用来记录以每一个数为最后一个数的最大长度，另一个储存最大长度的情况下的上一个数。
    错误的状态转移方程： a[i] = a[j] + 1 (a[i] == b[i])
    显然是错误的，于是我还考虑了下最长有多种情况的情况，用set储存上一个数，还是错误（毕竟想法就不太对）。

  • 于是隔了一天还是没想起来，于是百度了下题解，找到了一个不错的博客：题解
    可以看出来这篇博客风格也照抄了一下233，分析的很清楚，然后自己拿纸模拟了一遍，感觉这么简单的题怎么没想出来……

分析过程：

  • 用a[i][j]二维数组储存状态，i代表以第几个数结束，j代表倒数第二个数。
  • 状态转移方程：dp[i][j] = dp[j][k] + 1 (a[k]==a[i])
  • 看巨巨的题解K在状态转移的过程中就可以找到了。

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
#include <iostream>
#define MAX 4123
using namespace std;

int data[MAX];
int dp[MAX][MAX];

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> data[i];
    }

    int ans = 1;
    for (int i = 1; i <= n; i++)
    {
        int k = -1;
        for (int j = 1; j < i; j++)
        {
            if (k == -1)
                dp[i][j] = 2;
            else
                dp[i][j] = dp[j][k] + 1;
            if (data[i] == data[j])
                k = j;
            if (ans < dp[i][j])
                ans = dp[i][j];
        }
    }
    cout << ans;
}

#暴力遍历代码：
看题解之前想碰碰运气写的暴力代码，时间复杂度O(n^3)，当然TLE啦……

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

set<int> check;
vector<int> store;
int data[41234];
int n;

int scan(int a, int b)
{
    int judge = 0;
    int sum = 0;
    for (int i = 0; i < n; i++)
    {
        if (judge == 0 && (data[i] == a || data[i] == b) || data[i] == judge)
        {
            if (data[i] == a)
            {
                judge = b;
            }
            if (data[i] == b)
            {
                judge = a;
            }
            sum++;
        }
    }
    return sum;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> data[i];
        if (check.count(data[i]) == 0)
        {
            check.insert(data[i]);
            store.push_back(data[i]);
        }
    }
    int ans = 0;
    for (int i = 0; i < store.size(); i++)
    {
        for (int j = i; j < store.size(); j++)
        {
            int t = scan(data[i], data[j]);
            ans = ans > t? ans:t;
        }
    }
    cout << ans;
}