Posted in ACM-ICPC, Dynamic Programming

CF 474D Flowers

/* 7/14/2018
* Problem: http://codeforces.com/problemset/problem/474/D
* Solution: Dp. dp[i] = dp[i-1] + dp[i-k]. One state can be transferred to from two sources: 1. eat only white flower from the i-k day 2. otherwise.
* Notes: 1. Remember to mod the MOD every time there’s a summing process.
2. The result of a mod can be negative.
* A little bit gibber-gabber:
For both the notes, I KNEW it but I now don’t..??
What is the point of everything..
*/

#include
using namespace std;

int main() {
	int t, k;
	cin >> t >> k;
	long long ind[100005] = {0}, sum[100005] = {0};
	int MOD = 1000000007;
	for (int i = 0; i < k; i++) {
		ind[i] = 1;
	}
	for (int i = k; i <= 100005; i++) {
		ind[i] = (ind[i - 1] + ind[i - k]) % MOD;
	}
	sum[0] = 1;
	for (int i = 0; i  a >> b;
		long long ans = (sum[b] - sum[a - 1]) % MOD;
		if (ans < 0) {
			ans += MOD;
		}
		cout << ans << endl;
	}
	return 0;
}


Posted in Dynamic Programming

CF 431C k-Tree

2/8/2018
Problem: http://codeforces.com/problemset/problem/431/C
Solution: DP. We can generalie the problem into, divided number n as the sum of a couple numbers less than k. All so, one of them must be greater or equal to d.
So, we construct a 2-D dp with 0 or 1 denoting whether there already is one number greater or equal to d as the 2nd dimension.


#include
using namespace std;

int main() {
    int n, k, d;
    cin >> n >> k >> d;
    long long dp[105][2] = {0};
    long long mod = 1e9 + 7;
    dp[0][0] = 1;
    dp[0][1] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            if (i < j) break;
            if (j < d) {
                dp[i][0] = (dp[i][0] + dp[i - j][0]) % mod;
                dp[i][1] = (dp[i][1] + dp[i - j][1]) % mod;
            } else {
                dp[i][1] = (dp[i][1] + dp[i - j][0] + dp[i - j][1]) % mod;
            }
        }
    }
    cout << dp[n][1];
    return 0;
}

Posted in DFS, Dynamic Programming

PKU 7 Skiing

Problem: http://acmicpc.openjudge.cn/practice/007/


#include<iostream>
#include<cstring>
using namespace std;
int a[105][105] = {0};
int dp[105][105] = {0};
int dx[5] = {-1, 0, 0, 1};
int dy[5] = {0, -1, 1, 0};
int r, c;

int dfs(int x, int y) {
	if (dp[x][y] > 0) {
		return dp[x][y];	
	}	
	int tmp = 0;
	for (int i = 0; i < 4; i++) {
		int xx = x + dx[i];
		int yy = y + dy[i];
		if (xx > 0 && xx <= r && yy > 0 && yy <= c && a[xx][yy] < a[x][y]) {
			tmp = max(tmp, dfs(xx, yy) + 1);
		}
	} 
	return tmp;
}

int main() {
	cin >> r >> c;
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			cin >> a[i][j];
		}
	}
	int mx = 0;
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			dp[i][j] = dfs(i, j);
			// cout << dp[i][j] << ' ';
			if (dp[i][j] > mx) {
				mx = dp[i][j];
			} 
		}
		// cout << endl;
	}
	cout << mx + 1;
	return 0;
}

Posted in Dynamic Programming

CF 812B Sagheer, the Hausmeister

6/1/2017
Problem: http://codeforces.com/contest/812/problem/B
Solution: 2-D DP. Record the optimised steps for each floor and whether it’s
from left stair or right.
Note: There’re several cases I didn’t realize in the first begninning.
1. The top floor doesn’t need to be reached if there’s no light there.
2. There’s one special case when all the lights are turned off.
3. The case of only one floor has light and is also the bottom floor
needs special attention.
Others: It’s my first time doing a dp in a real contest! And what’s more, I got
a general idea how to truly write it! (Though didn’t pass because of
those special cases above, which I didn’t take into consideration.)
Anyway, it feels good.


#include<iostream>
#include<cmath>
using namespace std;
#define MAX 2000;

int main() {
	int dp[20][100] = {0};
	int n, m;
	cin >> n >> m;
	string s[20];
	for (int i = 1; i <= n; i++) {
		cin >> s[i];
		// cout << s[i] << endl;
	}
	int last;
	bool stop = true;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (s[i][j] == '1') {
//				cout << i << ' ' << j << endl;
				last = i;
				stop = false;
				break;
			}
		}
		if (!stop) {
			break;
		}
	} 
	for (int i = 1; i <= last - 1; i++) {
		for (int j = 0; j <= 1; j++){
			dp[i][j] = MAX;
		}
	}
	for (int i = n; i >= 1; i--) {
			int left1 = 0, left2 = 0, right1 = 0, right2 = 0;
			int leftp = m + 1, rightp = 0;
			bool first = true;
			// cout << s[i] << endl;
			for (int k = 1; k <= m; k++) {
				// cout << s[i][k] << ' ';
				if (s[i][k] == '1') {
					if (first) {
						leftp = k;
						first = false;
					}
					rightp = k;
				} 
			}
			if (i == last) {
				if (i == n) {
					cout << (rightp > (m - leftp + 1)? rightp: m - leftp + 1);
					return 0;
				}
				dp[last][0] = dp[last + 1][0] + rightp;
				dp[last][1] = dp[last + 1][1] + (m - leftp + 1);
				cout << (dp[last][1] < dp[last][0]? dp[last][1]: dp[last][0]);
				return 0;
			}
		 	// cout << dp[i - 1][0] << endl;
//		 	cout << leftp << ' ' << rightp << endl;
			left1 = dp[i + 1][0] + 2 * rightp + 1;
			left2 = dp[i + 1][1] + m + 2;
			right1 = dp[i + 1][1] + 2 * (m - leftp + 1) + 1;
			right2 = dp[i + 1][0] + m + 2;
//			cout << left1 << ' ' << left2 << ' ' << right1 << ' ' << right2 << endl;
			if (i == n) {
				dp[i][0] = left1;
				dp[i][1] = right2;
				continue;
			}
			dp[i][0] = min(left1, left2);
			dp[i][1] = min(right1, right2);
//			cout << dp[i][0] << ' ' << dp[i][1] << endl;
//		cout << endl;
	}
	cout << 0;
	return 0;
}

Posted in Dynamic Programming

BZOJ 2431 Reversed pair sequence

2017/1/28
Problem: http://www.lydsy.com/JudgeOnline/problem.php?id=2431
Solution: 2-D dynamic programming


#include<iostream>
using namespace std;
int dp[1005][1005] = {0};
int sum[1005] = {0};

int main() {
	int n, k;
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		dp[i][0] = 1;
		sum[0] = dp[i-1][0];
		for (int j = 1; j <= k; j++) {
			sum[j] = sum[j-1] + dp[i-1][j];
		}
		for (int j = 1; j <= k; j++) {
			dp[i][j] = (sum[j] - sum[j-(i-1)-1]) % 10000;
		}
	}
	cout << dp[n][k];
	return 0;
}