Fork me on GitHub

DP合集

Posted on | | Views:

石子合并

区间$DP$,入门题.环状$DP$先考虑线段.
我们用一个区间$[l,r]$表示石子,意义为该石子是由$[l,r]$区间的石子合并而来.
显然,最终一定只剩一堆石子$[l,r]$,且$\exists k$使得$[l,r]$先合并为$[l,k]$和$[k+1,r]$再合并为$[l,r]$.
于是我们可以很自然的想到从左右端点重合的区间(即单个元素)开始向上递推.
由于最大值最小值情况相同,所以只讨论最大值.
于是,设$f_{i,j}$表示把区间$[l,r]$合并起来能得到的最大值.
于是我们枚举断点就行了,不断递推即可.我们发现,转移需要快速求区间和.
所以还需要一个前缀和,记前缀和为$s_i$.
于是得到转移方程:
$$f_{i,j}=max(f_{i,j},f_{i,k}+f_{k+1,j}+s_j-s_{i-1})$$
$f$数组的初值显然为$0$.
线段考虑完成之后,考虑环状怎么做.
显然,原数组倍长断环成链即可.
$Code:$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
#define MEM(x,y) memset ( x , y , sizeof ( x ) )
#define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i)
#define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i)
#define pii pair < int , int >
#define one first
#define two second
#define rint read<int>
#define int long long
#define pb push_back

using std::queue ;
using std::set ;
using std::pair ;
using std::max ;
using std::min ;
using std::priority_queue ;
using std::vector ;
using std::swap ;
using std::sort ;
using std::unique ;
using std::greater ;

template < class T >
    inline T read () {
        T x = 0 , f = 1 ; char ch = getchar () ;
        while ( ch < '0' || ch > '9' ) {
            if ( ch == '-' ) f = - 1 ;
            ch = getchar () ;
        }
       while ( ch >= '0' && ch <= '9' ) {
            x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ;
            ch = getchar () ;
       }
   return f * x ;
}

const int M = 500 ;
const int inf = 0x7f7f7f7f ;
int n , v[M] , f[M][M] , g[M][M] , m , sum[M] ;
int maxn , minn = inf ;

signed main (int argc , char * argv[]) {
    n = rint () ; m = n << 1 ;
    rep ( i , 1 , n ) { v[i] = rint () ; v[i+n] = v[i] ; }
    rep ( i , 1 , m ) sum[i] = sum[i-1] + v[i] ;
    per ( i , m - 1 , 1 ) rep ( j , i + 1 , i + n - 1 ) {
        g[i][j] = inf ;
        rep ( k , i , j - 1 ) {
            f[i][j] = max ( f[i][j] , f[i][k] + f[k+1][j] + sum[j] - sum[i-1] ) ;
            g[i][j] = min ( g[i][j] , g[i][k] + g[k+1][j] + sum[j] - sum[i-1] ) ;
        }
    }
    rep ( i , 1 , n ) { maxn = max ( maxn , f[i][i+n-1] ) ; minn = min ( minn , g[i][i+n-1] ) ; }
    printf ("%lld\n%lld\n" , minn , maxn ) ;
    system ("pause") ; return 0 ;
}

ZROI#1007

也是看起来非常不可做的一个题.

仔细思考,发现了一个很$coooooooooool$的事情:

他是不是让我求最小独立集覆盖…

一个独立集覆盖是指把图划分成若干个子集,每个子集里的点两两互不连通.

然后你$2^n$枚举子集,记录是不是一个独立集,然后在独立集上$DP$.

你就令$f_S$表示点集为$S$时的最小独立集覆盖.

显然,每次可以从它一个是独立集的子集转移过来,取一个$min$就完了(最长路最短).

最后的答案是$f_{U}-1$,其中$U$是全集.为什么减一啊?

因为最长路是边数啊…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
#define MEM(x,y) memset ( x , y , sizeof ( x ) )
#define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i)
#define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i)
#define pii pair < int , int >
#define one first
#define two second
#define rint read<int>
#define int long long
#define pb push_back

using std::queue ;
using std::set ;
using std::pair ;
using std::max ;
using std::min ;
using std::priority_queue ;
using std::vector ;
using std::swap ;
using std::sort ;
using std::unique ;
using std::greater ;

template < class T >
    inline T read () {
        T x = 0 , f = 1 ; char ch = getchar () ;
        while ( ch < '0' || ch > '9' ) {
            if ( ch == '-' ) f = - 1 ;
            ch = getchar () ;
        }
       while ( ch >= '0' && ch <= '9' ) {
            x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ;
            ch = getchar () ;
       }
   return f * x ;
}

const int N = 20 ;
const int MAXS = 1 << 20 ;
int n , m , ans , s[N] ;
int g[MAXS] , f[MAXS] , cnt ;
bool e[N][N] ;

inline bool judge () {
    rep ( i , 1 , cnt ) rep ( j , 1 , cnt )
        if ( e[s[i]][s[j]] || e[s[j]][s[i]] ) return false ;
    return true ;
}

signed main (int argc , char * argv[]) {
    n = rint () ; m = rint () ;
    rep ( i , 1 , m ) {
        int u = rint () , v = rint () ;
        e[u][v] = e[v][u] = true ;
    }
    int maxsize = 1 << n ;
    for (int i = 0 ; i < maxsize ; ++ i) {
        cnt = 0 ;
        for (int j = 0 ; j < n ; ++ j)
            if ( i & ( 1 << j ) )
                s[++cnt] = j + 1 ;
        g[i] = judge () ;
    }
    MEM ( f , 0x7f ) ; f[0] = 0 ;
    for (int i = 0 ; i < maxsize ; ++ i) {
        for (int j = i ; j ; j = ( j - 1 ) & i )
            if ( ! g[j] ) continue ;
            else f[i] = min ( f[i] , f[i^j] + 1 ) ;
    }
    printf ("%lld\n" , f[maxsize-1] - 1 ) ;
    return 0 ;
}

LuoGuP1439
这个题并非只是简单的$\Theta(n^2)$的$LCS$.
我们发现直接$\Theta(n^2)$的$LCS$显然过不去高达$10^5$的数据.
但这题给了个奇妙的性质,它给的是两个排列.
也就是说,两个排列中的数字是相同的,唯一不同的就是数字的位置.
如果我们把第一个排列作为规定的大小顺序,那么我们发现,答案就是第二个排列在这个大小顺序下的$LIS$.
为什么呢?因为如果在第二个串中一个子序列是上升的,那么它在原序列中也一定是这样排列的.因为我们是按照第一个排列的顺序规定的大小.
所以就只需要映射完跑一遍$\Theta(n\times log_2n)$的$LIS$即可.
正好说一下$\Theta(n\times log_2n)$的$LIS$叭.
先来$\Theta(n^2)$叭.
令$f_i$表示以$i$结尾的最长上升子序列的长度.
转移显然.
$$f_i=max_{j\in [1,i]\&\&v_j<v_i}{f_j}+1$$
我们发现这个状态是很难进行推广的.
于是考虑去改变状态.
令$f_i$表示长度为$i$的最长上升子序列的结尾元素目前可能的最小值.
因为我们当前最长上升子序列的结尾元素肯定是越小越好,这样我们才有更多的”空间”去放别的数字.
考虑这样如何转移:
令当前长度是$cnt$.
如果有$f_{cnt}<v_i$,则直接放入当前最长上升子序列的末尾,$++cnt$.
否则,考虑调整,由于$v_i\le f_{cnt}$,所以在长度较小的上升子序列中可能存在一个位置可供$v_i$使用.
即把某个子序列中不如$v_i$的结尾元素替换为$v_i$.
二分实现即可,显然$f$数组具有单调性.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
#define MEM(x,y) memset ( x , y , sizeof ( x ) )
#define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i)
#define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i)
#define pii pair < int , int >
#define one first
#define two second
#define rint read<int>
#define int long long
#define pb push_back

using std::queue ;
using std::set ;
using std::pair ;
using std::max ;
using std::min ;
using std::priority_queue ;
using std::vector ;
using std::swap ;
using std::sort ;
using std::unique ;
using std::greater ;

template < class T >
    inline T read () {
        T x = 0 , f = 1 ; char ch = getchar () ;
        while ( ch < '0' || ch > '9' ) {
            if ( ch == '-' ) f = - 1 ;
            ch = getchar () ;
        }
       while ( ch >= '0' && ch <= '9' ) {
            x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ;
            ch = getchar () ;
       }
   return f * x ;
}

const int N = 1e5 + 100 ;

int n , v[N] , rk[N] , f[N] , cnt ;

signed main (int argc , char * argv[]) {
    n = rint () ; rep ( i , 1 , n ) rk[rint()] = i ;
    rep ( i , 1 , n ) v[i] = rint () ; f[0] = 0 ;
    rep ( i , 1 , n ) {
        if ( rk[v[i]] > f[cnt] ) f[++cnt] = rk[v[i]] ;
        else {
            int pos = std::lower_bound ( f + 1 , f + cnt + 1 , rk[v[i]] ) - f ;
            f[pos] = rk[v[i]] ;
        }
    }
    printf ("%lld\n" , cnt ) ;
    system ("pause") ; return 0 ;
}

最大子段和
水题.不知道为什么要写一遍,可能是太闲了叭(闲可不是好现象).
我直接上方程了:
令$f_i$表示$1$到$i$中的最大子段和是多少.
$$f_i=max(f_{i-1}+v[i],v[i])$$完了.
其实这个还可以扩展至区间查询.很不巧,我会.是用线段树去维护.
虽然这不具有直接的区间可合并性,但我们可以考虑最大子段和在合并的时候的构成.
显然,构成有以下几种:
左区间的前缀,左区间的后缀+右区间的前缀,右区间的后缀,整个左区间+右区间的前缀,整个右区间+左区间的后缀,整个区间,左区间中部,右区间中部.
对,只需要$pushup$的时候考虑这几种情况就行了.不过目前我还完全不会修改..只会静态的.
至于这个的例题,有:静态区间查询最大子段和
原题代码
$Code:$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
#define MEM(x,y) memset ( x , y , sizeof ( x ) )
#define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i)
#define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i)
#define pii pair < int , int >
#define one first
#define two second
#define rint read<int>
#define int long long
#define pb push_back
#define db double

using std::queue ;
using std::set ;
using std::pair ;
using std::max ;
using std::min ;
using std::priority_queue ;
using std::vector ;
using std::swap ;
using std::sort ;
using std::unique ;
using std::greater ;

template < class T >
    inline T read () {
        T x = 0 , f = 1 ; char ch = getchar () ;
        while ( ch < '0' || ch > '9' ) {
            if ( ch == '-' ) f = - 1 ;
            ch = getchar () ;
        }
       while ( ch >= '0' && ch <= '9' ) {
            x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ;
            ch = getchar () ;
       }
   return f * x ;
}

const int N = 2e5 + 100 ;

int n , v[N] , f[N] ;

signed main (int argc , char * argv[]) {
    n = rint () ;
    rep ( i , 1 , n ) v[i] = rint () ;
    f[0] = 0 ; int ans = - 0x7f7f7f7f ;
    rep ( i , 1 , n ) f[i] = max ( f[i-1] + v[i] , v[i] ) ;
    rep ( i , 1 , n ) ans = max ( ans , f[i] ) ;
    printf ("%lld\n" , ans ) ;
    system ("pause") ; return 0 ;
}

加强版代码:
$Code:$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <cstdlib>
#include <cstdio>
#define ls ( rt << 1 )
#define rs ( rt << 1 | 1 )
#define mid ( ( l + r ) >> 1 )
#define int long long

const int N = 1e5 + 5 ;

template < class T >
	inline T max ( T __A , T __B ) { return __A > __B ? __A : __B ; }

struct seg {
	int left , right , data ;
	int ldata , rdata , mdata ;
} t[(N<<2)] ;

int n , m , v[N] ;

inline void pushup (int rt) {
	t[rt].data = t[ls].data + t[rs].data ;
	t[rt].ldata = max ( t[ls].ldata , t[ls].data + t[rs].ldata ) ;
	t[rt].rdata = max ( t[rs].rdata , t[rs].data + t[ls].rdata ) ;
	t[rt].mdata = max ( t[ls].ldata , max ( t[rs].rdata , t[ls].rdata + t[rs].ldata ) ) ;
	t[rt].mdata = max ( t[rt].mdata , max ( t[ls].mdata , t[rs].mdata ) ) ;
	return ;
}

inline void prim (int rt , int val) { t[rt].data = t[rt].ldata = t[rt].rdata = t[rt].mdata = val ; return ; }

inline void build (int rt , int l , int r) {
	t[rt].left = l ; t[rt].right = r ;
	if ( l == r ) { prim ( rt , v[l] ) ; return ; }
	build ( ls , l , mid ) ; build ( rs , mid + 1 , r ) ;
	pushup ( rt ) ; return ;
}

inline seg query (int rt , int ll , int rr) {
	int l = t[rt].left , r = t[rt].right ;
	if ( ll <= l && r <= rr ) return t[rt] ;
	if ( rr <= mid ) return query ( ls , ll , rr ) ;
	else if ( ll > mid ) return query ( rs , ll , rr ) ;
	else {
		seg lans = query ( ls , ll , rr ) , rans = query ( rs , ll , rr ) ;
		seg ans ; ans.data = lans.data + rans.data ;
		ans.ldata = max ( lans.ldata , lans.data + rans.ldata ) ;
		ans.rdata = max ( rans.rdata , rans.data + lans.rdata ) ;
		ans.mdata = max ( lans.ldata , max ( rans.rdata , lans.rdata + rans.ldata ) ) ;
		ans.mdata = max ( ans.mdata , max ( lans.mdata , rans.mdata ) ) ;
		return ans ;
	}
}

signed main () {
	scanf ("%lld" , & n ) ;
	for (int i = 1 ; i <= n ; ++ i) scanf ("%lld" , & v[i] ) ;
	scanf ("%lld" , & m ) ; build ( 1 , 1 , n ) ;
	while ( m -- ) {
		register int u , v ;
		scanf ("%lld%lld" , & u , & v ) ;
		printf ("%lld\n" , query ( 1 , u , v ).mdata ) ;
	}
	return 0 ;
}

咕咕咕~

分享到： 收藏夹 复制网址 邮件 微信 QQ空间 腾讯微博 豆瓣 一键分享 更多