题解：第一题：我写的指针线段树，但是被卡了， 但是数组线段树不会，因为不用建树
这道题用并查集，从后往前染色，则不能覆盖，把一段颜色放在一个并查集中，O(N)的修改，我们让这段颜色的father指向他们这段的右端点，表示我下一次染色只能从右端点右边的一个开始；
#include <bits/stdc++.h> const int M = 1000000 + 5; int n, k; using namespace std; int vis[M], lf[M], rg[M], c[M], fa[M]; void read(int &x){ x=0;int f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c<='9'&&c>='0'){x=x*10+c-'0';c=getchar();} x*=f; } int find(int a){ if(fa[a]==a) return a; return fa[a]=find(fa[a]) ; } void uni(int a,int b){ if(find(a)!=find(b)) fa[fa[a]]=fa[b] ; } void paint(int now, int co){ vis[now] = co; if(now != 1 && vis[now-1])uni(now-1, now); if(now != n && vis[now+1])uni(now, now+1); } int main() { freopen("paint.in","r",stdin); freopen("paint.out","w",stdout); scanf("%d%d", &n, &k); for(int i = 1; i <= k; i++) read(lf[i]), read(rg[i]), read(c[i]); for(int i = 1; i <= n; i++)fa[i] = i; for(int i = k; i >= 1; i--){ int now = lf[i]; while(now <= rg[i]){ if(!vis[now]) paint(now, c[i]); now = find(now) + 1; } } for(int i = 1; i <= n; i++)printf("%d ", vis[i]); return 0; }
第二题：我们想的dp dp[j][i] = max (dp[k][j] + 1) 如果i,j,k连成的线合法，我们只需要最后的两个点就好了；
但是这样是N^3的， 过不了；我们想办法省去一维: dp[i] = max (dp[j] + 1),那我们必须保证转移到j的线再加上i-j这条线合法，构建
凸壳的边满足的条件是：犄角递增； 我们N*N枚举边的犄角（cmath : atan2(vec.y, vec.x) ）排序，按这个顺序建凸壳一定合法；我们用dp[i][j]表示以j结尾的凸壳边最多有多少条边； 更新它就用max dp[?][i] ，维护一个桶，O(1)，当再次来到i就构成了一个凸壳；
#include <bits/stdc++.h> const int M = 100000 + 5; using namespace std; void read(int &x){ x=0;int f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c<='9'&&c>='0'){x=x*10+c-'0';c=getchar();} x*=f; } struct Point{ int x, y; }p[305]; Point operator -(const Point &a, const Point &b){ return (Point){a.x - b.x, a.y - b.y}; } struct Edge{ double ang; int from, to;}G[300*300]; bool cmp(Edge a, Edge b){return a.ang < b.ang;} int dp[305][305], tong[305]; int main(){ // freopen("convex.in","r",stdin); // freopen("convex.out","w",stdout); int n, tot = 0; scanf("%d", &n); for(int i = 1; i <= n; i++)scanf("%d%d",&p[i].x, &p[i].y); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(i != j){ Point tmp = p[j] - p[i]; G[++tot].ang = atan2(tmp.y, tmp.x); G[tot].from = i; G[tot].to = j; } sort(G+1, G+1+tot, cmp); int ans = 0; if(n <= 3){ printf("%d ", n); return 0; } for(int h = 1; h <= n; h++){ memset(dp, 0, sizeof(dp)); memset(tong, 0x8f, sizeof(tong)); tong[h] = 0; for(int i = 1; i <= tot; i++){ int from = G[i].from, to = G[i].to; dp[from][to] = tong[from] + 1; tong[to] = max(tong[to], dp[from][to]); //printf("%d %d %d %d %d ", i, dp[from][to], from, to, tong[to]); } ans = max(ans, tong[h]); } printf("%d ",ans); }
第三题：贪心+dp
首先电视连续与不连续与他们排在任何一种种类后面没有关系， 所以我们把一个种类放在一起；对于连续与不连续的电视节目其实就是看他们分成了几段，如果分成3段，我们就会有3个b的收益，所以我们选3个最大的b, 剩下的a贪心要最大的；就可以预处理出每种颜色分成k段的最大收益；
dp[i][k]表示考虑了前i种电视分成了k段的最大收益，限制是什么，对于单个电视分的段数 <= ceil(k /2);以下是std
/* * m.cpp * * Created on: Oct 28, 2013 * Author: acm */ #include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <string> #include <vector> #include <algorithm> using namespace std; const int MAX_N = 600 + 10, INF = ~0U >> 2; struct TV { int t, a, b; int id; void read(int id) { this->id = id; cin >> t >> a >> b; } bool operator<(const TV&o) const { return b - a > o.b - o.a; } }; struct TVSet { vector<TV> a; void add(TV o) { a.push_back(o); } vector<int> maxret; int color, n; vector<vector<int> > dp, how; void update(int i, int j, int hw, int c) { // cout << i << " " << j << " " << c << " " << dp[i][j] << endl; if (c > dp[i][j]) { dp[i][j] = c; how[i][j] = hw; } } void doit() { n = a.size(); color = a[0].t; dp.assign(n + 1, vector<int>(n + 1, -INF)); how.assign(n + 1, vector<int>(n + 1)); sort(a.begin(), a.end()); dp[0][0] = 0; for (int i = 0; i < n; ++i) { TV me = a[i]; for (int j = 0; j <= n; ++j) { int c = dp[i][j]; // cout << i << " " << j << " " << c << endl; if (c == -INF) continue; if (j > 0) update(i + 1, j, 0, c + me.a); update(i + 1, j + 1, 1, c + me.b); update(i + 1, j, -1, c); } } maxret.assign(n + 1, 0); for (int i = 0; i <= n; ++i) { maxret[i] = dp[n][i]; // cerr << maxret[i] << endl; } } vector<vector<TV> > chains; void buildIt(int k) { chains.clear(); int i = n, j = k; vector<pair<int, TV> > op; while (i > 0) { if (how[i][j] == -1) { --i; continue; } if (how[i][j] == 0) { op.push_back(make_pair(0, a[i - 1])); --i; continue; } if (how[i][j] == 1) { op.push_back(make_pair(1, a[i - 1])); --i, --j; continue; } } int chk = 0; for (int i = 0; i < op.size(); ++i) { pair<int, TV> t = op[op.size() - 1 - i]; // cerr << t.second.id << endl; if (t.first == 0) { chains[0].push_back(t.second); chk += t.second.a; } else { chains.push_back(vector<TV>()); chains.back().push_back(t.second); chk += t.second.b; } } // cout << chk << " " << maxret[k] << endl; // cout << chains.size() << " " << k << endl; } bool operator<(const TVSet&o) const { return a.size() < o.a.size(); } }; TVSet set[MAX_N]; int n; vector<TVSet> tvsets; vector<vector<vector<int> > > dp; int main() { freopen("tv.in","r",stdin); freopen("tv.out","w",stdout); cin >> n; for (int i = 0; i < n; ++i) { TV t; t.read(i); --t.t; set[t.t].add(t); } for (int i = 0; i < n; ++i) { if (set[i].a.size()) { tvsets.push_back(set[i]); } } sort(tvsets.begin(), tvsets.end()); for (int i = 0; i < tvsets.size(); ++i) { tvsets[i].doit(); } dp.resize(tvsets.size() + 1); dp[0] = vector<vector<int> >(1, vector<int>(1, 0)); // dp[0][0][0] = 0; int curSum = 0, curMax = 0; for (int i = 0; i < tvsets.size(); ++i) { int nextSum = curSum + tvsets[i].n; int nextMax = tvsets[i].n; if(i>0) dp[i-1].clear(); dp[i + 1] = vector<vector<int> >(nextSum + 1, vector<int>(nextMax + 1, -INF)); TVSet&set = tvsets[i]; for (int j = 0; j <= curSum; ++j) { for (int k = 0; k <= curMax; ++k) { int c = dp[i][j][k]; if (c == -INF) continue; for (int me = 0; me <= set.n; ++me) { int nc = c + set.maxret[me]; int nk = max(me, k); if (nc > dp[i + 1][j + me][nk]) { dp[i + 1][j + me][nk] = nc; } } } } curSum = nextSum, curMax = nextMax; } int best = 0; for (int j = 0; j <= curSum; ++j) { for (int k = 0; k <= curMax; ++k) if (k + k - 1 <= j) { if (dp[tvsets.size()][j][k] > best) { best = dp[tvsets.size()][j][k]; } } } cout << best << endl; }