250pt
定義大小為N的三角形, 是由若干個(gè)等大的圓形構(gòu)成的, 高度和底寬為N.
三角形的每個(gè)圓染三種顏色 r,g,b,相接觸的圓不能染同種顏色.
問有R個(gè)r顏色的球, G個(gè)g顏色的球和B個(gè)b顏色的球, 最多能染多少個(gè)大小為N的三角形.
r+g+b不爆long long, N不爆int
算法分析:
不會(huì)
500pt:
大小為n*m(n,m<30)的矩陣, 有L,P,.,三種格子, 畫兩個(gè)互不相交的矩形, 使兩個(gè)矩形L和P的差不超過D, 問這兩個(gè)矩形最多能包含的L和P的和.
算法分析:
暴力的話是n^8, GG
不難想到, 兩個(gè)矩形之間要么可以劃一條水平分割線, 要么可以畫一條豎直分割線.
于是預(yù)處理所有的分割線,左右側(cè)差為d的最多包含的L和P. 預(yù)處理過程是O(n^6).
然后枚舉兩個(gè)矩形的L和P的差, 再枚舉分割線, 復(fù)雜度O(n^5).
預(yù)處理的常數(shù)非常小, 極限數(shù)據(jù)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
西月弦 閱讀(398)
評(píng)論(1) 編輯 收藏 引用 所屬分類:
解題報(bào)告