题意：n个点，找出一个矩形，使其边界上包含尽量多的点。
思路：1.部分枚举 -> 枚举上下界（将n个点的纵坐标单独排序）。
2.枚举n个点 -> 枚举k条竖线（按照横坐标排序）。
3.ans = max{ lef[ i ] - lef[ j ] + on[ j ] + on2[ i ] }， 显然要取左侧最大的 “- lef[ j ] + on[ j ]” ， 维护该最大值（M）该问题可以O（n）解决。
1 #include2 using namespace std; 3 4 const int N = 100+5; 5 int n, y[N], lef[N], on[N], on2[N]; 6 struct point{ 7 int x, y; 8 bool operator<(const point& other)const{ 9 return x < other.x;10 }11 }p[N];12 13 int solve(){14 int ans = 0;15 sort(y, y + n);16 sort(p, p + n);17 int m = unique(y, y+n) - y;18 if(m <= 2) return n;19 for(int a = 0; a < m; a++){20 for(int b = a+1; b < m; b++){21 int ymin = y[a], ymax = y[b], k = 0;///a new up and low.22 lef[k] = on[k] = on2[k] = 0;23 for(int i = 0; i < n; i++){24 if(i == 0 || (p[i].x != p[i-1].x)){ ///a new line.25 k++;26 on[k] = on2[k] = 0;27 lef[k] = lef[k-1]+on2[k-1]-on[k-1];28 }29 if(p[i].y > ymin && p[i].y < ymax) on[k]++;30 if(p[i].y >= ymin && p[i].y <= ymax) on2[k]++;31 }32 if(k <= 2) return n;///i=0...n-1 -> <=2 -> n.33 int M = 0;34 for(int i = 1; i <= k; i++){ ///i=1...k35 ans = max(ans, lef[i]+on2[i]+M);36 M = max(M, on[i]-lef[i]);37 }38 }39 }40 return ans;41 }42 43 int main()44 {45 int kase = 0;46 while(~scanf("%d", &n) && n){47 for(int i = 0; i < n; i++){48 scanf("%d %d", &p[i].x, &p[i].y);49 y[i] = p[i].y;50 }51 printf("Case %d: %d\n", ++kase, solve());52 }53 return 0;54 }
题意：约瑟夫环问题变形，n个人围坐一圈按序号排排好，第一次删除序号为m的老哥,之后每数k个人删除一次，求幸存者的序号。
思路：1.递推！ f[ n ] = （f[ n - 1 ] + k） %n. （f[ n ]表示共n个人时，幸存者的序号）n个人从 0 数到 k - 1 删去一个后(即为f[ n - 1]时的情形)，从第k个人开始从 0 ~ n - 1 编号, 那么偏移就是 k - 0, f[ 0 ] = 0。复杂度O(n)。
2.为了计算方便把序号减一，那么第一次本应删去的是序号为（k - 1）的老哥，因此偏移为 m - (k-1), 然后再把序号加一即可。
1 #include2 using namespace std; 3 4 int main() 5 { 6 int n, m, k, ans; 7 while(~scanf("%d%d%d", &n,&k,&m) && (n||m||k)){ 8 ans = 0; 9 for(int i = 2; i <= n; i++) ans = (ans + k) %i;10 ans = (ans + m-(k-1)) %n;11 if(ans <= 0) ans += n;12 printf("%d\n", ans);13 }14 return 0;15 }
题意：求A、B的LCS，两个序列的长度超级无敌巨长！但是！系列中无重复元素！！！
思路：1.由于序列长度可达250^2=62500,O(mn)的LCS解法显然行不通。
2.序列中无重复元素，给A中每个元素编号，然后将B的元素按A的编码方式保存，于是就转化为LIS问题，可O（nlogn）解决！！！
1 #include2 using namespace std; 3 4 const int inf = 1e9+7; 5 const int N = 250 * 250; 6 int n, p, q, d[N], id[N], b[N], g[N]; 7 8 int main() 9 {10 int t, x, kase = 0;11 scanf("%d", &t);12 while(t--){13 memset(id, 0, sizeof(id));14 scanf("%d%d%d", &n,&p,&q);15 for(int i = 1; i <= p+1; i++){16 scanf("%d", &x);17 id[x] = i;18 }19 p = 0;20 for(int i = 1; i <= q+1; i++){ ///q+1...+1...21 scanf("%d", &x);22 if(id[x]) b[p++] = id[x];23 }24 int ans = 0;25 memset(g, inf, sizeof(g));26 for(int i = 0; i < p; i++){27 int pos = lower_bound(g+1, g+p+1, b[i]) - g;28 d[i] = pos;29 g[pos] = b[i];30 ans = max(ans, d[i]);31 }32 printf("Case %d: %d\n", ++kase, ans);33 }34 return 0;35 }
题意：从左侧或右侧取数，两个人都尽力使自己取得数的和最大，问sumA-sumB。
思路：总和一定，一人得分越高另一人得分就越低，因此无论怎么取，任意时刻游戏的状态都是原始序列的一段连续子序列。。。
1 #include2 using namespace std; 3 4 const int N = 100+5; 5 int A[N], d[N][N], f[N][N], g[N][N], s[N]; 6 7 int main() 8 { 9 int n;10 s[0] = 0;11 while(~scanf("%d", &n) && n){12 for(int i = 1; i <= n; i++){13 scanf("%d", &A[i]);14 s[i] = s[i-1] + A[i];15 }16 for(int i = 1; i <= n; i++) d[i][i] = f[i][i] = g[i][i] = A[i];17 for(int L = 1; L < n; L++){18 for(int i = 1, j; i+L <= n; i++){19 j = i+L;20 int m = min(f[i+1][j], min(0, g[i][j-1]));21 d[i][j] = s[j] - s[i-1] - m;22 f[i][j] = min(d[i][j], f[i+1][j]);23 g[i][j] = min(d[i][j], g[i][j-1]);///gggggggggggggg...24 }25 }26 printf("%d\n", (d[1][n]<<1) - s[n]);27 }28 return 0;29 }
明明已经看了lrj的代码还是顺手把数组名g写成f wa了一发。。。