1~N连续的白格子，给出若干操作，分为两种，在[1,ai]里选择xi个白格子染成黑色，以及在[ai,n]里选择xi个白格子染成黑色。问把最多的格子染成黑色至少需要多少次操作。
先只考虑第一种操作，显然优先把最左边的填满，对于第二种操作，优先把最右边的填满。这就转化成了背包模型，做完两遍后合并背包即可。
1 #include <string.h> 2 #include <stdio.h> 3 #include <algorithm> 4 #define INF 0x3f3f3f3f 5 #define MAXN 1005 6 using namespace std; 7 struct oper{ 8 int op, ai, xi; 9 bool operator <(const oper& o) const { 10 return op < o.op || (op == o.op && ai < o.ai); 11 } 12 }p[MAXN]; 13 int cas, n, m, op[2], tx, ty, tz; 14 int d1[MAXN], d2[MAXN]; 15 int main(){ 16 scanf("%d", &cas); 17 for (int ca = 1; ca <= cas; ca++) { 18 scanf("%d%d", &n, &m); 19 op[0] = op[1] = 0; 20 for (int i = 0; i < m; i++) { 21 scanf("%d%d%d", &tx, &ty, &tz); 22 p[i].op = tx, p[i].ai = ty, p[i].xi = tz; 23 op[tx-1]++; 24 } 25 std::sort(p, p + m); 26 memset(d1, 0x3f, sizeof d1); d1[0] = 0; 27 memset(d2, 0x3f, sizeof d2); d2[0] = 0; 28 for (int i = 0; i < op[0]; i++) 29 for (int j = p[i].ai - p[i].xi; j >= 0; j--) 30 if(d1[j]!=INF) d1[j+p[i].xi] = min(d1[j+p[i].xi], d1[j]+1); 31 for (int i = m-1; i >= op[0]; i--) 32 for (int j = n - p[i].ai - p[i].xi+1; j >= 0; j--) 33 if(d2[j]!=INF) d2[j+p[i].xi] = min(d2[j+p[i].xi], d2[j]+1); 34 int ans1 = 0, ans2 = 0; 35 for (int i = 0; i <= n; i++) 36 for (int j = n-i; j >=0; j--) 37 if(d1[i]!=INF&&d2[j]!=INF&&(i+j>ans1||i+j==ans1&&d1[i]+d2[j]<ans2)) ans1 = i+j, ans2 = d1[i]+d2[j]; 38 39 printf("Case %d: %d %d\n", ca, ans1, ans2); 40 } 41 return 0; 42 }