Regionals 2012 :: Asia - Dhaka

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：

2012Dhaka

题目链接：UVALive 比赛链接：VJ B：

Wedding of Sultan

就是一颗树的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
/* ***************

Author        :kuangbin

Created Time  :2014/7/21 18:09:57

File Name     :E:\2014ACM\区域赛练习\2012\2012Dhaka\B.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

char str[10000];

int du[30];

int pre[30];

int main()

{

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    int T;

	int iCase = 0;

	scanf("%d",&T);

	while(T--)

	{

		iCase++;

		scanf("%s",str);

		memset(du,0,sizeof(du));

		int now = str[0] - 'A';

		pre[now] = -1;

		int len = strlen(str);

		for(int i = 1;i < len;i++)

		{

			if(now == str[i] - 'A')

				now = pre[now];

			else

			{

				du[now]++;

				pre[str[i]-'A'] = now;

				now = str[i]-'A';

				du[now] = 1;

			}

		}

		printf("Case %d\n",iCase);

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

			if(du[i])

				printf("%c = %d\n",'A'+i,du[i]);

	}

    return 0;

}
C：

Memory Overflow

水题一个。 

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
/* ***************

Author        :kuangbin

Created Time  :2014/7/21 18:20:39

File Name     :E:\2014ACM\区域赛练习\2012\2012Dhaka\C.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

char str[1000];

int main()

{

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    int T;

	int iCase = 0;

	int n,k;

	scanf("%d",&T);

	while(T--)

	{

		iCase++;

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

		int ans = 0;

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

		{

			for(int j = 1;j <= k && j <= i;j++)

				if(str[i-j] == str[i])

				{

					ans++;

					break;

				}

		}

		printf("Case %d: %d\n",iCase,ans);

	}

    return 0;

}
D：

Laptop Chargers

关于第一问，其实只要产生的大于消耗的，就可以一直运行下去。 第二问的时候，要二分时间，然后去判断这个时间产生和消耗的关系。

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
/* ***************

Author        :kuangbin

Created Time  :2014/7/21 18:25:02

File Name     :E:\2014ACM\区域赛练习\2012\2012Dhaka\D.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

const double eps = 1e-8;

struct Node

{

	int C,T,R;

	void input()

	{

		scanf("%d%d%d",&C,&T,&R);

	}

}node[110];

int main()

{

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    int n,Q;

	int iCase = 0;

	while(scanf("%d%d",&n,&Q) == 2)

	{

		if(n == 0 && Q == 0)break;

		iCase++;

		printf("Case %d:\n",iCase);

		int C;

		scanf("%d",&C);

		double sum = 0.0;

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

		{

			node[i].input();

			sum += (double)node[i].C/node[i].T;

		}

		printf("%d\n",(int)ceil(sum/C));

		int m;

		while(Q--)

		{

			scanf("%d",&m);

			double l = 0, r = 100010.0;

			while(r-l >= eps)

			{

				double mid = (l+r)/2;

				double tmp = 0.0;

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

					tmp += max(0.0,mid*node[i].C/node[i].T-node[i].R);

				if(tmp <= (double)m*C*mid)

					l = mid+eps;

				else r = mid-eps;

			}

			if(l >= 100000)printf("-1.000\n");

			else printf("%.3lf\n",l);

		}

	}

    return 0;

}

E:

Poker End Games

高斯消元求解。 直接建立方程。 然后解方程就可以了。 变量是n+m+1个变量。

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
/* ***************

Author        :kuangbin

Created Time  :2014/7/21 19:55:49

File Name     :E:\2014ACM\区域赛练习\2012\2012Dhaka\E.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

#define eps 1e-9

const int MAXN=330;

double a[MAXN][MAXN],x[MAXN];

int equ,var;

/*

*返回0表示无解，1表示有解

*/

int Gauss()

{

    int i,j,k,col,max_r;

    for(k=0,col=0;k<equ&&col<var;k++,col++)

    {

        max_r=k;

        for(i=k+1;i<equ;i++)

          if(fabs(a[i][col])>fabs(a[max_r][col]))

            max_r=i;

        if(fabs(a[max_r][col])<eps)return 0;

        if(k!=max_r)

        {

            for(j=col;j<var;j++)

              swap(a[k][j],a[max_r][j]);

            swap(x[k],x[max_r]);

        }

        x[k]/=a[k][col];

        for(j=col+1;j<var;j++)a[k][j]/=a[k][col];

        a[k][col]=1;

        for(i=0;i<equ;i++)

          if(i!=k)

          {

              x[i]-=x[k]*a[i][k];

              for(j=col+1;j<var;j++)a[i][j]-=a[k][j]*a[i][col];

              a[i][col]=0;

          }

    }

    return 1;

}

int main()

{

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    int T;

	int iCase = 0;

	int n,m;

	scanf("%d",&T);

	while(T--)

	{

		iCase++;

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

		equ = var = n+m+1;

		memset(a,0,sizeof(a));

		a[0][0] = 1.0; x[0] = 0.0;

		a[n+m][n+m] = 1.0; x[n+m] = 0.0;

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

		{

			a[i][i] = 1.0;

			x[i] = 1.0;

			int tmp = min(i,n+m-i);

			a[i][i-tmp] -= 0.5;

			a[i][i+tmp] -= 0.5;

		}

		Gauss();

		double ans1 = x[n];

		memset(a,0,sizeof(a));

		a[0][0] = 1.0; x[0] = 0.0;

		a[n+m][n+m] = 1.0; x[n+m] = 1.0;

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

		{

			a[i][i] = 1.0;

			x[i] = 0.0;

			int tmp = min(i,n+m-i);

			a[i][i-tmp] -= 0.5;

			a[i][i+tmp] -= 0.5;

		}

		Gauss();

		double ans2 = x[n];

		printf("Case %d: %.6lf %.6lf\n",iCase,ans1,ans2);

	}

    return 0;

}

F：

Overlapping Characters

水题。 直接暴力。 就是题意比较麻烦，卧槽

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
#include <stdio.h>

#include <algorithm>

#include <iostream>

#include <queue>

#include <set>

#include <string.h>

#include <map>

#include <vector>

#include <string>

#include <math.h>

using namespace std;

char str[40][20][50];

char s[100];

map<char,int>mp;

int a[100];

int main()

{

	//freopen("in.txt","r",stdin);

	//freopen("out.txt","w",stdout);

	int n,q;

	while(scanf("%d%d",&n,&q) == 2)

	{

		mp.clear();

		scanf("%s",s);

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

			mp[s[i]] = i;

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

			for(int j = 0;j < 17;j++)

				scanf("%s",str[i][j]);

		for(int k = 0;k < q;k++)

		{

			scanf("%s",s);

			int m = strlen(s);

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

				a[i] = mp[s[i]];

			printf("Query %d: ",k+1);

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

			{

				bool flag = false;

				for(int x = 0;x < 16;x++)

					for(int y = 0;y < 43;y++)

					{

						if(flag)break;

						if(str[a[i]][x][y] == '*')

						{

							bool ff = true;

							for(int j = 0;j < m;j++)

								if(j != i && str[a[j]][x][y] == '*')

								{

									ff = false;

									break;

								}

							if(ff)

							{

								flag = true;

								break;

							}

						}

					}

				if(flag)printf("Y");

				else printf("N");

			}

			printf("\n");

		}

	}

	return 0;

}
G:

Reduce the Maintenance Cost

首先是进行缩点，把桥都找出来。 其实需要分配的就是这些桥。 缩点以后形成一个有向无环图。 就是很多颗树。 对于每颗树， 桥的分配从下到上。桥尽量分配给底下的点，不能分在分给顶上。 二分答案，然后进行判断。 写起来比较麻烦，非常锻炼代码能力。

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
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
/* ***************

Author        :kuangbin

Created Time  :2014/7/21 18:40:44

File Name     :E:\2014ACM\区域赛练习\2012\2012Dhaka\G.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

const int MAXN = 10010;//点数

const int MAXM = 40010;//边数，因为是无向图，所以这个值要*2

struct Edge

{

    int to,next;

	int w;

    bool cut;//是否是桥标记

	int to_node;

}edge[MAXM];

int head[MAXN],tot;

int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];//Belong数组的值是1~block

int Index,top;

int block;//边双连通块数

bool Instack[MAXN];

int bridge;//桥的数目

void addedge(int u,int v,int w)

{

    edge[tot].to = v;edge[tot].next = head[u];edge[tot].cut=false;

	edge[tot].w = w;

    head[u] = tot++;

}

struct Node//存的是桥相关信息

{

	int u,v;

	int w;

	long long val;

	Node(int _u = 0,int _v = 0,int _w = 0)

	{

		u = _u;

		v = _v;

		w = _w;

	}

}node[MAXM];

void Tarjan(int u,int pre)

{

    int v;

    Low[u] = DFN[u] = ++Index;

    Stack[top++] = u;

    Instack[u] = true;

    for(int i = head[u];i != -1;i = edge[i].next)

    {

        v = edge[i].to;

        if(v == pre)continue;

        if( !DFN[v] )

        {

            Tarjan(v,u);

            if( Low[u] > Low[v] )Low[u] = Low[v];

            if(Low[v] > DFN[u])

            {

				node[bridge] = Node(u,v,edge[i].w);

				edge[i].to_node = bridge;//根据边的编号指向桥的编号

				edge[i^1].to_node = bridge;

                bridge++;

                edge[i].cut = true;

                edge[i^1].cut = true;

            }

        }

        else if( Instack[v] && Low[u] > DFN[v] )

            Low[u] = DFN[v];

    }

    if(Low[u] == DFN[u])

    {

        block++;

        do

        {

            v = Stack[--top];

            Instack[v] = false;

            Belong[v] = block;

        }

        while( v!=u );

    }

}

void init()

{

    tot = 0;

    memset(head,-1,sizeof(head));

}

vector<int>vec[MAXN];//存的缩点后的图

vector<int>vec2[MAXN];//缩点后的图边对于的桥的编号

int dep[MAXN];//深度

int num[MAXN];//连通块大小

int tot_num[MAXN];//缩点后子树大小

void dfs(int u,int pre,int d)//计算深度，以及子树大小

{

	dep[u] = d;

	tot_num[u] = num[u];

	int sz = vec[u].size();

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

	{

		int v = vec[u][i];

		if(v == pre)continue;

		dfs(v,u,d+1);

		tot_num[u] += tot_num[v];

	}

}

int TOT;

void dfs2(int u,int pre)//算每个桥的信息

{

	int sz = vec[u].size();

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

	{

		int v = vec[u][i];

		if(v == pre)continue;

		int id = vec2[u][i];

		node[id].val = (long long)node[id].w*tot_num[v]*(TOT-tot_num[v]);

		dfs2(v,u);

	}

}

bool cmp(Node a,Node b)//按照深度从大到小排序

{

	return dep[Belong[a.v]] > dep[Belong[b.v]];

}

int iv[MAXN];

long long pv[MAXN];

void solve(int n)

{

	memset(DFN,0,sizeof(DFN));

	memset(Instack,false,sizeof(Instack));

	Index = top = block = 0;

	bridge = 0;

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

		if(DFN[i] == 0)

			Tarjan(i,0);

	for(int i = 1;i <= block;i++)

	{

		vec[i].clear();

		vec2[i].clear();

	}

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

		for(int j = head[i];j != -1;j = edge[j].next)

			if(edge[j].cut)

			{

				vec[Belong[i]].push_back(Belong[edge[j].to]);

				vec2[Belong[i]].push_back(edge[j].to_node);

			}

	memset(num,0,sizeof(num));

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

		num[Belong[i]]++;

	memset(dep,-1,sizeof(dep));

	for(int i = 1;i <= block;i++)

		if(dep[i] == -1)

		{

			dfs(i,-1,0);

			TOT = tot_num[i];

			dfs2(i,-1);

		}

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

	{

		if(dep[Belong[node[i].u]] > dep[Belong[node[i].v]])

			swap(node[i].u,node[i].v);

	}

	sort(node,node+bridge,cmp);

	//二分答案

	long long ans;

	long long l = 0;

	long long r = 1000000000000000000LL;

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

		if(iv[i] > l)

			l = iv[i];

	while(l <= r)

	{

		long long mid = (l+r)/2;

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

			pv[i] = iv[i];

		bool flag = true;

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

		{

			if(pv[node[i].v] + node[i].val <= mid)

				pv[node[i].v] += node[i].val;

			else if(pv[node[i].u] + node[i].val <= mid)

				pv[node[i].u] += node[i].val;

			else 

			{

				flag = false;

				break;

			}

		}

		if(flag)

		{

			ans = mid;

			r = mid-1;

		}

		else l = mid+1;

	}

	cout<<ans<<endl;

}

int main()

{

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    int T;

	int n,m;

	scanf("%d",&T);

	int iCase = 0;

	while(T--)

	{

		iCase++;

		init();

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

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

			scanf("%d",&iv[i]);

		int u,v,w;

		while(m--)

		{

			scanf("%d%d%d",&u,&v,&w);

			addedge(u,v,w);

			addedge(v,u,w);

		}

		printf("Case %d: ",iCase);

		solve(n);

	}

    return 0;

}
H：

Team Mathematics Olympiad

典型的概率DP。 状态压缩去表示每个人答了多少题，以及前一题是答对还是答错。

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
#include <stdio.h>

#include <algorithm>

#include <iostream>

#include <queue>

#include <set>

#include <string.h>

#include <map>

#include <vector>

#include <string>

#include <math.h>

using namespace std;

const double INF = 1e30;

double p[10][100];

bool f[100];

double dp[1100000][2];

bool vis[1100000][2];

int base;

int n,m;

int encode(int a[])

{

	int ret = 0;

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

	{

		ret *= base;

		ret += a[i];

	}

	return ret;

}

void decode(int a[],int s)

{

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

	{

		a[i] = s%base;

		s /= base;

	}

}

double solve(int s,int pre)

{

	if(vis[s][pre])return dp[s][pre];

	vis[s][pre] = true;

	int num[10];

	decode(num,s);

	int tot = 0;

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

		tot += num[i];

	if(tot == m)

	{

		int Max = num[0],Min = num[0];

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

		{

			Max = max(Max,num[i]);

			Min = min(Min,num[i]);

		}

		if(Max - Min > 1)return dp[s][pre] = -INF;

		else return dp[s][pre] = 0.0;

	}

	dp[s][pre] = -INF;

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

	{

		if(num[i]+1 >= base)continue;

		num[i]++;

		int ns = encode(num);

		if(solve(ns,0) < -10)

		{

			num[i]--;

			continue;

		}

		double pp = p[i][tot];

		if(f[tot] && pre == 0) pp = 0;

		dp[s][pre] = max(dp[s][pre],solve(ns,0)(1-pp) + (solve(ns,1)+1)pp);

		num[i]--;

	}

	return dp[s][pre];

}

int main()

{

	//freopen("in.txt","r",stdin);

	//freopen("out.txt","w",stdout);

	int T;

	int iCase = 0;

	scanf("%d",&T);

	while(T--)

	{

		iCase++;

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

		memset(f,false,sizeof(f));

		int nn;int u;

		scanf("%d",&nn);

		while(nn--)

		{

			scanf("%d",&u);

			u--;

			f[u] = true;

		}

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

			for(int j = 0;j < m;j++)

				scanf("%lf",&p[i][j]);

		base = m/n;

		if(m%n)base += 2;

		else base++;

		memset(vis,false,sizeof(vis));

		printf("Case %d: %.4lf\n",iCase,solve(0,0));

	}

	return 0;

}
I：

Learning Vector

按照顺序进行排序。 之后就是简单的DP了。 很简单的题。

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
/* ***************

Author        :kuangbin

Created Time  :2014/7/21 20:11:55

File Name     :E:\2014ACM\区域赛练习\2012\2012Dhaka\I.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

struct Node

{

	int x,y;

}node[100];

bool cmp(Node a,Node b)

{

	return a.y*b.x > a.x*b.y;

}

int dp[55][55][3000];

int main()

{

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    int T;

	int n,k;

	scanf("%d",&T);

	int iCase = 0;

	while(T--)

	{

		iCase++;

		int sum = 0;

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

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

		{

			scanf("%d%d",&node[i].x,&node[i].y);

			sum += node[i].y;

		}

		sort(node+1,node+n+1,cmp);

		memset(dp,-1,sizeof(dp));

		dp[0][0][0] = 0;

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

			for(int j = 0;j <= k && j <= i;j++)

				for(int L = 0;L <= sum;L++)

				{

					if(dp[i][j][L] < 0)continue;

					dp[i+1][j][L] = max(dp[i+1][j][L],dp[i][j][L]);

					if(j < k)

						dp[i+1][j+1][L+node[i+1].y] = max(dp[i+1][j+1][L+node[i+1].y],dp[i][j][L]+L*node[i+1].x*2+node[i+1].x*node[i+1].y);

				}

		int ans = 0;

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

			ans = max(ans,dp[n][k][i]);

		printf("Case %d: %d\n",iCase,ans);

	}

    return 0;

}
------ 本文结束------
  • 本文作者： kuangbin
  • 本文链接： 271.html
  • 版权声明： 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处！
0%