acm-DP整理

  1 一、背包
  2 1.各种01背包
  3 void leastOne_Pack(int id, int num ) {//至少取一个；
  4     int i, j, c, v ;
  5     for(i = 1 ; i <= num ; i ++ )
  6     {
  7         scanf("%d %d", &c, &v) ;
  8         for(j = T ; j >= c ; j -- ) 
  9         {// 下面的顺序不能交换；
 10             if(f[id][j-c] != -1 ) f[id][j] = getMax(f[id][j], f[id][j-c] + v ) ;
 11             if(f[id-1][j-c] != -1 ) f[id][j] = getMax(f[id][j], f[id-1][j-c] + v ) ;
 12         }
 13     }
 14 }
 15 void mostOne_Pack(int id, int num ) { // 最多取一个；
 16     int i, j ;
 17     int c[N], v[N] ;
 18     for(i = 1 ; i <= num ; i ++ ) scanf("%d %d", &c[i], &v[i] ) ;
 19     for(i = 0 ; i <= T ; i ++ ) f[id][i] = f[id-1][i] ;
 20     for(i = 1 ; i <= num ; i ++ )
 21     {
 22         for(j = T ; j >= c[i] ; j --)
 23             if(j >= c[i] && f[id-1][j-c[i]] != -1 ) f[id][j] = getMax(f[id][j], f[id-1][j-c[i]] + v[i] ) ;
 24     } 
 25 }
 26 void common_Pack(int id, int num ){ // 一般的01背包；
 27     int i, j, c, v ;
 28     for(i = 0 ; i <= T ; i ++ ) f[id][i] = f[id-1][i] ;
 29     for(i = 1 ; i <= num ; i ++ )
 30     {
 31         scanf("%d %d", &c, &v) ;
 32         for(j = T ; j >= c ; j -- ) 
 33             if(f[id][j-c] != -1 ) f[id][j] = getMax(f[id][j], f[id][j-c] + v ) ;
 34     }
 35 }
 36 2.完全背包
 37 void Comlepte_Pack(){
 38 　　for(i = 0 ; i < n ; i ++ )
 39 　　{
 40 　　            scanf("%d %d", &p, &w ) ;
 41 　　            for(j = w ; j <= vol ; j ++ ) 
 42                   f[j] = f[j] < f[j-w] + p ? f[j] : f[j-w] + p ;
 43 　　}
 44 }
 45 3.依赖背包
 46 struct Goods{
 47     int c, v ;
 48 } g[61][61] ;
 49 void dependent_Pack(int vol, int gn ){
 50     int i, j, k, mc, mv, c, v ;
 51     for(j = 1, f[0] = 0 ; j <= vol ; j ++ ) f[j] = -1 ;
 52     for(i = 1 ; i <= gn ; i ++ )
 53     {
 54         if( !num[i]) continue ;
 55         mc = g[i][0].c ; mv = g[i][0].v*mc ;
 56         for(j = 1, h[0] = 0 ; j <= vol-mc ; j++ ) h[j] = -1 ;
 57         for(k = 1 ; k < num[i] ; k ++ )//10背包，相当于得到0 - vol-mc种物品；
 58         {
 59             c = g[i][k].c ; v = g[i][k].v*c ;
 60             for(j = vol-mc ; j >= c ; j -- )
 61                 if(h[j-c] != -1 ) h[j] = h[j] > h[j-c]+v ? h[j] : h[j-c]+v ;
 62         }
 63         for(j = vol ; j >= mc ; j -- )//对于1 - vol-mc种物品，至多选择一种；
 64         {
 65             for(k = 0 ; k <= j-mc ; k ++ )
 66             {
 67                 if(h[k] == -1 ) continue ;
 68                 c = k+mc ; v = h[k]+mv ;
 69                 if(j >= c && f[j-c] != -1 ) f[j] = f[j] > f[j-c]+v ? f[j] : f[j-c]+v ;
 70             }
 71         }
 72     }
 73 }
 74 二、极大化
 75 1.极大化算法一
 76 以障碍点经过的边作为矩形的左边界，一直向右边扫描
 77 struct Point{
 78     int x, y ;
 79 }p[MAXN] ;
 80 bool comp(Point a, Point b){
 81     if(a.x == b.x) return a.y < b.y ;
 82     else return a.x < b.x ;
 83 }
 84 int DP(){// h,d 表示扫描线的上下端点高度
 85     int i, j, h, d, s ;
 86     int ans = 0 ;
 87     for (i = 1; i <= n; i ++) //枚举障碍点
 88     {
 89         h = W ; d = 0 ; 
 90         for(j = i+1 ; j <= n && h > d ; j ++)
 91         {
 92             if(p[i].x == p[j].x || p[j].y > h || p[j].y < d) continue ; 
 93             // 扫描得到的矩形一定要经过i点
 94             s = (h-d)*(p[j].x-p[i].x) ;
 95             ans = ans > s ? ans : s ;
 96             if(p[j].y < h && p[j].y >= p[i].y) h = p[j].y ; 
 97             //保证向前扫描一定经过i点
 98             if(p[j].y > d && p[j].y <= p[i].y) d = p[j].y ;
 99         }
100     }
101     return ans ;
102 }
103 int solve(){
104     int i, j, tx, ans = 0 ;
105     while(~scanf("%d %d", &L, &W))
106     {
107         scanf("%d", &n) ; memset(pre, 0, sizeof(pre)) ;
108         for(i = 1 ; i <= n ; i ++) 
109         {
110             scanf("%d %d", &p[i].x, &p[i].y) ; pre[p[i].y]  = 1 ;
111         }
112         for(tx = 0, i = 1 ; i <= W ; i ++)
113         {
114             tx ++ ;
115             if(pre[i]) 
116             {
117                 ans = ans > tx ? ans : tx ;
118                 tx = 0 ;
119             }
120         }
121         ans = ans*L ;
122         p[++n].x = 0 ; p[n].y = 0 ; p[++n].x = 0 ; p[n].y = W ;
123         p[++n].x = L ; p[n].y = 0 ; p[++n].x = L ; p[n].y = W ;
124         sort(p+1, p+1+n, comp) ;
125         tx = DP() ; printf("%d
", ans > tx ? ans : tx) ;
126     }
127   }
128 
129 
130 
131 
132 
133 2.算法二
134  a.悬线的定义：上端点是障碍点或者边界的线段 ；
135  (1) h[i][j]表示以点(i,j)结束的悬线的最大长度；
136  (2) l[i][j]表示悬线(i,j)左移量，r[i][j]表示其右移量；
137  (3) ml[i][j]表示点(i,j)左边最近的障碍点位置，没有时为左边界。同理……
138  b.dp方程：
139  (1) 如果点(i-1,j)为障碍点或边界(i=0)：
140      h[i][j] = 1,l[i][j] = L(大矩形长度),r[i][j] = 0；
141  (2) 如果点(i-1,j)不为障碍点:
142      h[i][j]=h[i-1][j]+1, 
143      l[i][j]=max(l[i-1][j],ml[i][j]), 
144      r[i][j]=min(r[i-1][j],mr[i][j]).
145 description ：取最大周长矩形，该矩形要么由一种颜色覆盖，要么由两种颜色交叉覆盖。
146 int h[3][MAXN][MAXN], l[3][MAXN][MAXN], r[3][MAXN][MAXN] ;
147 int mr[3][MAXN][MAXN], ml[3][MAXN][MAXN] ; 
148 //[i][j] 左右边最近的异色点，没有异色点为边界位置
149 int map[MAXN][MAXN] ;
150 void getTable(){//初始化数组
151     int i, j ;
152     for(i = 1 ; i <= n ; i ++)
153     {
154         map[i][0] = map[i][1] ; map[i][m+1] = map[i][m] ;
155         ml[0][i][0] = 0 ; mr[0][i][m+1] = m+1 ;
156         for(j = 1 ; j <= m ; j ++)
157         {
158             ml[1][i][j] = ml[0][i][j] = 
159             (map[i][j]==map[i][j-1]) ? ml[0][i][j-1] : j-1 ;
160             ml[2][i][j] = 
161             (map[i][j]^map[i][j-1]) ? ml[2][i][j-1] : j-1 ;
162         }
163         for(j = m ; j ; j --)
164         {
165             mr[1][i][j] = mr[0][i][j] =
166             (map[i][j]==map[i][j+1]) ? mr[0][i][j+1] : j+1 ;
167             mr[2][i][j] = 
168              (map[i][j]^map[i][j+1]) ? mr[2][i][j+1] : j+1 ;
169         }
170     }
171 }
172 int DP(){
173     int i, j, k, ans = 0 ;
174     for (i = 1 ; i <= n ; i ++)
175         for (j = 1 ; j <= m ; j ++)
176         {
177             for(k = 0 ; k < 3 ; k ++)
178             {
179                 if(k < 2 && (map[i][j] != k)) continue ;
180                 bool v = map[i][j]^map[i-1][j] ;
181                 if(i == 1 || ((2-k) && v) || (!(2-k) && !v) ) //特判
182                 {
183                     h[k][i][j] = 1 ;
184                     l[k][i][j] = ml[k][i][j] ;
185                     r[k][i][j] = mr[k][i][j] ;
186                 }
187                 else                {
188                     h[k][i][j] = h[k][i-1][j]+1 ;
189                     l[k][i][j] = max(l[k][i-1][j], ml[k][i][j]) ;
190                     r[k][i][j] = min(r[k][i-1][j], mr[k][i][j]) ;
191                 }
192                 ans = max(ans, 2*(r[k][i][j]-l[k][i][j]-1+h[k][i][j])) ;
193             }
194         }
195     return ans ;
196 }
197 int solve(){
198         getTable() ; printf("Case #%d: %d
", cas ++, DP()) ;
199   }
200 三、分数规划
201 1.二分法
202 double DP(double f){
203     int i ;
204     double ans ;
205     for(i = 1 ; i <= n ; i ++) d[i] = 1.0*a[i] - b[i]*f;
206     sum[0] = 0.0 ;
207     for(i = 1 ; i <= n ; i ++) sum[i] = sum[i-1] + d[i] ;
208     ans = sum[k] ; dp[k] = sum[k] ;
209     for(i = k+1 ; i <= n ; i ++)
210     {
211         dp[i] = max(sum[i]-sum[i-k], dp[i-1]+d[i]) ;
212         ans = max(ans, dp[i]) ;
213     }
214     return ans ;
215 }
216 double binary(double l, double r){
217     double mid ;
218     while(r-l > EPS)
219     {
220         mid = (l+r)/2.0 ;
221         if(DP(mid) > EPS) l = mid+EPS ;
222         else r = mid ;
223     }
224     return l ;
225 }
226 2.牛顿逼近法
227 void build(double s){
228     int i, j ;
229     for(i = 1 ; i <= n ; i ++)
230     for(j = 1 ; j <= n ; j ++)
231     {
232         map[i][j].d = map[i][j].l - s*map[i][j].c ;
233     }
234 }
235 double solve(){
236     int i ;
237     double s, ans = 1.0 ;
238     do    {
239         s = ans ;
240         build(s) ;
241         ans = kruskal(1) ;
242     }while(fabs(ans-s) > EPS) ;
243     return 1.0/ans ;
244 }
245 四、经典模型
246 1.LICS平方算法
247 int dp[MAXN][MAXN] ; // dp[i][j]表示a[1-i]到b[1-j]且以b[j]结尾的LCIS ；
248 int dp_LCIS(){
249     int i, j, max_l , ans = 0 ;
250     for(i = 1 ; i <= m ; i ++) dp[0][i] = 0 ;
251     for(i = 1 ; i <= n ; i ++)
252     {
253         max_l = 0 ;
254         for(j = 1 ; j <= m ; j ++)
255         {
256             dp[i][j] = dp[i-1][j] ;
257             if(a[i] > b[j]) max_l = max(max_l, dp[i-1][j]) ;
258             //因为相当于a[i] > b[k]与b[j] > b[k]等价( >= 是非递减)；
259             if(a[i] == b[j]) dp[i][j] = max_l + 1 ;
260         }
261         ans = max(ans, dp[i][m]) ;
262     }
263     return ans ;
264 }
265 2.最长回文序列
266 int solve(){ //最长回文子序列
267     int i, j, tmp ; 
268     memset(dp, 0, sizeof(dp)) ; 
269     for(i = 1 ; i <= 3*n ; i ++) dp[i][i] = 1 ; 
270     for(i = 3*n-1 ; i ; i --)
271     {
272         for(j = i+1 ; j <= 3*n ; j ++)
273         {
274             dp[i][j] = max(dp[i+1][j], dp[i][j-1]) ; 
275             tmp = dp[i+1][j-1] + 2*(ar[i] == ar[j]) ; 
276             dp[i][j] = max(dp[i][j], tmp) ; 
277         }
278     }
279     int ans = 1 ; 
280     for(i = n+1 ; i <= 2*n ; i ++) ans = max(ans, dp[i-n+1][i+n-1]) ;
281     return ans ; 
282 }
283 3.最短编辑距离
284 int solve(){//最短编辑距离
285     int i, j, tmp, mx = max(ls, lt) ;
286     for(i = 0 ; i <= ls ; i ++)
287         for(j = 0 ; j <= lt ; j ++) dp[i][j] = mx ;
288     for(i = 0 ; i <= mx ; i ++) dp[i][0] = dp[0][i] = i ;
289     for(i = 1 ; i <= ls ; i ++ )
290     {
291         for(j = 1 ; j <= lt ; j ++)
292         {
293             tmp = min(dp[i-1][j]+1, dp[i][j-1]+1) ;
294             if(s[i] == t[j]) dp[i][j] = min(dp[i][j], min(dp[i-1][j-1], tmp )) ;
295             else dp[i][j] = min(dp[i][j], min(tmp, dp[i-1][j-1] + 1)) ;
296         }
297     }
298     for(i = 1 ; i <= ls ; i ++) printf("%d ", dp[i][lt]) ; puts("") ;
299     return dp[ls][lt] ;
300 }
301 4.最长公共子序列个数
302 bool solve(){//最长公共子序列个数
303     int i, j ; bool d = 0 ;
304     memset(f[d], 0, sizeof(f[d])) ; memset(g[d], 0, sizeof(g[d])) ;
305     for(i = max(n, m) ; i >= 0 ; i --) g[d][i] = 1 ;
306     for(i = 1 ; i <= n ; i ++)
307     {
308         memset(f[!d], 0, sizeof(f[!d])) ; memset(g[!d], 0, sizeof(g[!d])) ;
309         g[!d][0] = 1 ;
310         for(j = 1 ; j <= m ; j ++)
311         {
312             if(s[i] == t[j])
313             {
314                 f[!d][j] = f[d][j-1] + 1 ;
315                 g[!d][j] = g[d][j-1] ;
316                 if(f[!d][j] == f[d][j])
317                    g[!d][j] = (g[!d][j] + g[d][j]) % MOD ;
318                 if(f[!d][j] == f[!d][j-1]) 
319                    g[!d][j] = (g[!d][j] + g[!d][j-1]) % MOD ;
320             }
321             else            
322              {
323                 f[!d][j] = max(f[d][j], f[!d][j-1]) ;
324                 if(f[!d][j] == f[d][j])
325                    g[!d][j] = (g[!d][j] + g[d][j]) % MOD ;
326                 if(f[!d][j] == f[!d][j-1]) 
327                    g[!d][j] = (g[!d][j] + g[!d][j-1]) % MOD ;
328                 if(f[!d][j] == f[d][j-1])
329                    g[!d][j] = ( g[!d][j] - g[d][j-1] + MOD) % MOD ;
330             }
331         }
332         d = !d ;
333     }
334     return d ;
335 }
View Code