250pt
定义大小为N的三角形, 是由若干个等大的圆形构成的, 高度和底宽为N.
三角形的每个圆染三种颜色 r,g,b,相接触的圆不能染同种颜色.
问有R个r颜色的球, G个g颜色的球和B个b颜色的球, 最多能染多少个大小为N的三角形.
r+g+b不爆long long, N不爆int
算法分析:
不会
500pt:
大小为n*m(n,m<30)的矩阵, 有L,P,.,三种格子, 画两个互不相交的矩形, 使两个矩形L和P的差不超过D, 问这两个矩形最多能包含的L和P的和.
算法分析:
暴力的话是n^8, GG
不难想到, 两个矩形之间要么可以划一条水平分割线, 要么可以画一条竖直分割线.
于是预处理所有的分割线,左右侧差为d的最多包含的L和P. 预处理过程是O(n^6).
然后枚举两个矩形的L和P的差, 再枚举分割线, 复杂度O(n^5).
预处理的常数非常小, 极限数据1s出解.
1 #include<vector>
2 #include<string>
3 #include<iostream>
4 #include<cstring>
5 using namespace std;
6 int col[35][2005][2];
7 int row[35][2005][2];
8 const int inf = ~0u>>2;
9 inline void chkmax(int &a,const int& b) {
10 if(a < b) a = b;
11 }
12 class FoxAndFlowerShopDivOne{
13 public : int theMaxFlowers(vector <string> num, int maxDiff){
14 int n = num.size(), m = num[0].size();
15 for(int i = 0; i <35;i++)
16 for(int j = 0; j<2005; j++)
17 for(int p = 0; p<2;p++)
18 col[i][j][p] = row[i][j][p] = -inf;
19 for(int i = 0; i< n; i++)
20 for(int j = 0; j< m; j++)
21 for(int x = 0; x<= i; x++)
22 for(int y = 0; y<= j; y++){
23 int suml = 0, sump = 0;
24 for(int p = x; p <= i; p++) for(int q = y ; q <= j; q++) suml += num[p][q] == 'L', sump += num[p][q] == 'P';
25 int sum = suml+sump;
26 int tmp = suml - sump + 1000;
27 chkmax(row[i][tmp][0], sum);
28 chkmax(row[x][tmp][1], sum);
29 chkmax(col[j][tmp][0], sum);
30 chkmax(col[y][tmp][1], sum);
31 }
32 for(int j = 0; j< 2005; j++){
33 for(int i = 1; i< n; i++)
34 chkmax(row[i][j][0],row[i-1][j][0]);
35 for(int i = n-2; i>=0; i--)
36 chkmax(row[i][j][1],row[i+1][j][1]);
37 for(int i = 1; i< m; i++)
38 chkmax(col[i][j][0],col[i-1][j][0]);
39 for(int i= m-2; i>=0; i--)
40 chkmax(col[i][j][1],col[i+1][j][1]);
41 }
42 int ans = -1;
43 for(int i = - n*m; i<=n*m; i++)
44 for(int j = -n*m; j<=n*m; j++) if(abs(i+j) <= maxDiff) {
45 for(int r = 0; r< n-1; r++){
46 chkmax(ans, row[r][i+1000][0] + row[r+1][j+1000][1]);
47 }
48 for(int c = 0; c< m-1; c++)
49 chkmax(ans, col[c][i+1000][0] + col[c+1][j+1000][1]);
50 }
51 return ans;
52 }
53 };
posted on 2012-08-17 13:17
西月弦 阅读(390)
评论(1) 编辑 收藏 引用 所属分类:
解题报告