lemonoil

OI__nothing is impossible

#清北学堂第一天——DP

###主讲人——胡泽聪

在我写这篇博客的时候，我已经从北京回到成都了，回顾这七天的学习，除了超出我现有知识体系的knowledge以外，更多的是了解了信息学竞赛究竟意味着什么，对我自己又有何意义。 伴随着感叹，我开始了整理。 ##DP（个人理解） 不同于数据结构和网络流（到现在还停留在模板题），dp是最让我震撼与头痛的，巧妙的思想，灵活的变形，与其他知识点纷繁复杂的搭配（特别是数论），吸引着一代代OIer。 ##DP的序章 ###CodeChef June13 LEMOUSE

https://www.codechef.com/JUNE13/problems/LEMOUSE

题目就略了，这道题目是dp，还是很明显的，但是如何做？用状压dp保存九宫格？曼哈顿距离是关键，回顾题目一只老鼠只会吓到大象一次，所以说，我们只需要记录走到这一步之前的f[i,j]来决定是否会重复记录已发现的老鼠，再仔细一想，对于dp[i,j]若在九宫格的四角上，那么我们只需要记录上一步是否被吓到就可以了。

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <stack>
#include <cmath>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#define mod  1000000007
#define PHI 1000000006
#define ull unsigned long long
#define ill long long int
#define pii pair<int,int>
#define pb(x) push_back(x)
#define F(i,a,n) for(i=(a);i<(n);++i)
#define FD(i,a,n) for(i=(a);i>=(n);--i)
#define S(x) scanf("%d",&x)
#define S1(x) scanf("%llu",&x)
using namespace std;
typedef unsigned long long int uint64;
 
int dp[101][101][3][3];
char s[101][101];
int n,m;
int aa[] = {0, 1};
int bb[] = {1, 0};
 
int f (int sx, int sy, int down, int right)
{
 
    down = min (down, 2);
    right = min (right, 2);
    int &result = dp[sx][sy][down][right];
    if (result != -1) {
        return result;
    }
 
    result = 0;
 
    if (down == 2) {
        if (sy-1 >= 0) {
            if (s[sx][sy-1] == '1') {
                result++;
            }
        }
    }
 
    if (right == 2) {
        if (sx-1 >= 0) {
            if (s[sx-1][sy] == '1') {
                result++;
            }
        }
    }
 
    if (sx == n-1 && sy == m-1) {
        return result;
    }
 
    int i,xx=1000000;
 
    F (i, 0, 2) {
        int px,py;
        px = sx + aa[i];    py = sy + bb[i];
        if (px == n || py == m) {
            continue;
        }
        if (s[px][py] == '1') {
            result++;
        }
        int r,d;
        r = right;   d = down;
        if (i == 0) {
            r++;
            d = 0;
        }
        if (i == 1) {
            d++;
            r = 0;
        }
        xx = min (xx, f (px, py, d, r));
    }
 
    result = result + xx;
    return result;
}
 
 
int main()
{
    int t;
    S (t);
    while (t--) {
        S (n);  S (m);
 
        int i,j;
        memset (dp, -1, sizeof(dp));
 
        F (i, 0, n) {
            scanf ("%s", &s[i]);
        }
 
 
        int x = f (0, 0, 0, 0);
        if (s[0][0] == '1') {
            x++;
        }
        printf ("%d\n", x);
 
    }
    return 0;
}

###TopCoder Open 2014 Round 1B L3 EagleInZoo

https://community.topcoder.com/stat?c=problem_statement&pm=13117

这道题有数学期望………………但是作为一道树上dp，我觉得很适合练手。首先这道题很明显有子问题，用dp[i,j]表示j只鹰从i节点出发留在树上的概率，所以dp[i,1]=1,当j>1时，若ci=0，则dp[i,j]=0。 然后就是dp方程了： dp[x,k]=$ \sum_{y\in_child \leaf(i\right)}\frac{1}{c_x} \sum_{i=0}^{k-2} \left( \frac{k-2}{i} \right) \left( \frac{1}{c_x} \right)^i \left( 1-\frac{1}{c_x} \right)^{k-2-i} $p[y,i+1] (还没有下载latex，先将就着看，应该看得懂，描述已经够通俗了……)

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 <functional>
#include <numeric>
#include <utility>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <bitset>
#include <string>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <cstring>
#include <ctime>
#include <climits>
using namespace std;
#define CHECKTIME() printf("%.2lf\n", (double)clock() / CLOCKS_PER_SEC)
typedef pair<int, int> pii;
typedef long long llong;
typedef pair<llong, llong> pll;
#define mkp make_pair
const int MAX_N = 51, MAX_K = 101;
double dp[MAX_N][MAX_K];
double C[MAX_K][MAX_K];		// 二项系数，注意：用 long long 会溢出
class EagleInZoo {
public:
	vector < vector<int> > childs;
	double rec(int v, int t)
	{
		if (1 == t) {
			return 1.0;
		}
		double & res = dp[v][t];
		if (res > -0.5) {
			return res;
		}
		if (childs[v].size() == 0 && t > 1) {	// 该节点无 child 且t > 1，最后一只一定无法停留
			res = 0;
			return res;
		}
		res = 0;
		for (int i = 0; i < childs[v].size(); i++) {
			int x = childs[v][i];
			int c = childs[v].size();
			for (int j = 0; j <= t - 2; j++) {
				res += (1.0 / c) * C[t-2][j] * pow(1.0 / c, j) * pow( 1.0 * (c-1) / c, t-2-j) * rec(x, j + 1);
			}
		}
		return res;
	}
	double calc(vector <int> parent, int K) {
		for (int i = 0; i < MAX_N; i++) {
			for (int j = 0; j < MAX_K; j++) {
				dp[i][j] = -1.0;
			}
		}
		childs.resize(parent.size() + 1);
		for (int i = 0; i < parent.size(); i++) {
			childs[ parent[i] ].push_back(i + 1);
		}
		// calculate C[]
		C[0][0] = 1;
		for (int i = 1; i <= K - 1; i++) {
			C[i][0] = C[i][i] = 1;
			for (int j = 1; j < i; j++) {
				C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
			}
		}
		return rec(0, K);
	}
};
//**复杂度O（nk^2）**

补充试题：

http://codeforces.com/contest/341/problem/C

https://www.codechef.com/APRIL14/problems/ANUCBC

##进击的DP ###CodeChef FEB14 LEMOVIE little elephant and movies

https://www.codechef.com/FEB14/problems/LEMOVIE

严格大于，就是最长上升子序列，先考虑互不相同，然后在想如何去重，用dp[i,j]表示插入前i大的数，激动值为j的方案数。 每组数的贡献值最多为1，且满足了后无效性，之后的数不会改变之前的dp。复杂度也就O(nk)。

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
84
85
86
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<climits>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stack>
#include<queue>
using namespace std;
 
#define FOR(i,a,b) 	for(int i= (int )a ; i < (int )b ; ++i)
#define rep(i,n) 	FOR(i,0,n)
#define INF		INT_MAX
#define ALL(x) 		x.begin(),x.end()
#define LET(x,a)	__typeof(a) x(a)
#define IFOR(i,a,b) 	for(LET(i,a);i!=(b);++i)
#define EACH(it,v) 	IFOR(it,v.begin(),v.end())
#define pb 		push_back
#define sz(x) 		int(x.size())
#define mp 		make_pair
#define fill(x,v)	memset(x,v,sizeof(x))
#define max(a,b)	((a)>(b)?(a):(b))
#define min(a,b)	((a)<(b)?(a):(b))
#define	si(n)		scanf("%d",&n)
#define pi(n)		printf("%d ",n)
#define pil(n)		printf("%d\n",n)
#define sd(n)		scanf("%lf",&n)
#define sl(n)		scanf("%lld",&n)
#define pl(n)		printf("%lld\n",n)
#define ss(n)		scanf("%s",n)
#define scan(v,n)	vector<int> v;rep(i,n){ int j;si(j);v.pb(j);}
#define mod (int)(1e9 + 7)
typedef pair<int,int> PI;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long LL;
LL dp[202][202][202],dp2[202][202][202];
int main()
{
	int i,j,n,t,k;
	for(si(t);t--;)
	{
		VI cnt,cum;
		si(n);
		si(k);
		cnt.resize(201);
		rep(i,n)
		{
			si(j);
			cnt[j]++;
		}
		fill(dp,0);
		fill(dp2,0);
		dp[0][0][0] = dp2[0][0][0] = 1;
		cum.pb(0);
		FOR(i,1,201)
			cum.pb(cum.back() + cnt[i]);
		LL ans = 0;
		rep(i,201)
		{
			rep(j,n+1)
			{
				rep(sum,cum[i]+1)
				{
					if(sum)
						dp[i][j][sum] = dp[i][j][sum-1]*(cum[i]-sum+1);
					if(j and sum)
					{
						dp[i][j][sum] += dp2[i-1][j-1][sum-1]*cnt[i];
						dp[i][j][sum] %= mod;
					}
					dp2[i][j][sum] = (dp[i][j][sum] + dp2[i-1][j][sum])%mod;
					if(j<=k and sum==n)
						ans = (ans + dp[i][j][sum])%mod;
				}
			}
		}
		cout << ans%mod << endl;
	}
	return 0;
}

###Codeforces Round #211(Div. 1):problem C Circling Round Treasures 一开始看到这道题的时候想到的是强连通分量，用trajan来缩点，但毕竟是dp题，缩点这种贪心的方式果然是有漏洞的（漏洞是什么请读者自己思考），然后就学习了射线法（本该是计算几何的内容）（话说知识点交叉是很频繁的啊，数据结构中讲了点分治…………），然后就可以判断点与多边形的位置关系，之后就dp大法好。

1
2

click it and link me

Launch CodeCogs Equation Editor