算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
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)  编辑 收藏 引用 所属分类: 解题报告

FeedBack:
# re: topcoder srm 552 div1 比赛小记
2012-08-17 22:16 | wu
我找规律过的- -,n%3==0 || n%3==2时,前n行三种颜色的球的数量是相同的,n%3==1的时候就是最顶上球的那种颜色多了一种
http://blog.csdn.net/haha593572013/article/details/7876600  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理