ডাইনামিক প্রোগ্রামিং এ হাতেখড়ি-৩ (কয়েন চেঞ্জ + রক ক্লাইম্বিং)
Problem:
1017. Staircases
11331 - The Joys of Farming
11137 - Ingenuous Cubrency
Others Problem Solution:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| ///http://www.lightoj.com/volume_showproblem.php?problem=1004 | |
| #include <bits/stdc++.h> | |
| using namespace std; | |
| #define INF 1<<30 | |
| #define endl '\n' | |
| #define maxn 100005 | |
| #define tc printf("Case %d: ", cs) | |
| #define tcn printf("Case %d:\n", cs); | |
| #define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); | |
| typedef long long ll; | |
| const double PI = acos(-1.0); | |
| #define dbg(x) cerr << #x << " = " << x << endl; | |
| #define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl; | |
| #define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl; | |
| #define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl; | |
| const int nx = 205; | |
| int grid[nx][nx]; | |
| int dp[nx][nx]; | |
| int n; | |
| int solve(int i, int j) | |
| { | |
| if (i > 0 && i <= 2 * n and j > 0 and j <= 2 * n) { | |
| if (dp[i][j] != -1) return dp[i][j]; | |
| int ret = 0; | |
| ret = max(ret, solve(i + 1, j) + grid[i][j]); | |
| if (i < n) ret = max(ret, solve(i + 1, j + 1) + grid[i][j]); | |
| else ret = max(ret, solve(i + 1, j - 1) + grid[i][j]); | |
| return dp[i][j] = ret; | |
| } | |
| else return 0; | |
| } | |
| int main() | |
| { | |
| //FASTIO | |
| ///* | |
| //double start_time = clock(); | |
| #ifndef ONLINE_JUDGE | |
| freopen("in.txt", "r", stdin); | |
| freopen("out.txt", "w", stdout); | |
| freopen("error.txt", "w", stderr); | |
| #endif | |
| //*/ | |
| int T; | |
| scanf("%d", &T); | |
| for (int cs = 1; cs <= T; cs++) { | |
| memset(dp, -1, sizeof dp); | |
| memset(grid, 0, sizeof grid); | |
| scanf("%d", &n); | |
| for (int i = 1; i <= n; i++) | |
| for (int j = 1; j <= i; j++) | |
| scanf("%d", &grid[i][j]); | |
| for (int i = n + 1; i < (2 * n); i++) | |
| for (int j = 1; j <= (2 * n - i); j++) | |
| scanf("%d", &grid[i][j]); | |
| printf("Case %d: %d\n", cs, solve(1,1)); | |
| } | |
| //double end_time = clock(); | |
| //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000); | |
| return 0; | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| ///https://codeforces.com/contest/118/problem/D | |
| #include <bits/stdc++.h> | |
| using namespace std; | |
| #define INF 1<<30 | |
| #define endl '\n' | |
| #define maxn 100005 | |
| #define tc printf("Case %d: ", cs) | |
| #define tcn printf("Case %d:\n", cs); | |
| #define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); | |
| typedef long long ll; | |
| const double PI = acos(-1.0); | |
| #define dbg(x) cerr << #x << " = " << x << endl; | |
| #define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl; | |
| #define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl; | |
| #define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl; | |
| int dp[101][101][2][11]; | |
| const int Mod = 1e8; | |
| int n1, n2, k1, k2; | |
| int solve(int footman, int horseman, int lastType, int last) | |
| { | |
| int ans = dp[footman][horseman][lastType][last]; | |
| if (ans == -1) { | |
| ans = 0; | |
| // Footman | |
| if (footman > 0) { | |
| if (lastType == 1) ans += solve(footman - 1, horseman, 0, 1); | |
| else if (last < k1) ans += solve(footman - 1, horseman, 0, last + 1); | |
| ans %= Mod; | |
| dp[footman][horseman][lastType][last] = ans; | |
| } | |
| // Horseman | |
| if (horseman > 0) { | |
| if (lastType == 0) ans +=solve(footman, horseman - 1, 1, 1); | |
| else if (last < k2) ans += solve(footman, horseman - 1, 1, last + 1); | |
| ans %= Mod; | |
| dp[footman][horseman][lastType][last] = ans; | |
| } | |
| if (footman == 0 && horseman == 0) ans = 1; | |
| } | |
| return ans; | |
| } | |
| int main() | |
| { | |
| // FASTIO | |
| ///* | |
| //double start_time = clock(); | |
| #ifndef ONLINE_JUDGE | |
| freopen("in.txt", "r", stdin); | |
| freopen("out.txt", "w", stdout); | |
| freopen("error.txt", "w", stderr); | |
| #endif | |
| //*/ | |
| memset(dp, -1, sizeof dp); | |
| scanf("%d %d %d %d", &n1, &n2, &k1, &k2); | |
| printf("%d\n", solve(n1, n2, 0, 0)); | |
| //double end_time = clock(); | |
| //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000); | |
| return 0; | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| ///http://www.lightoj.com/volume_showproblem.php?problem=1231 | |
| #include <bits/stdc++.h> | |
| using namespace std; | |
| #define INF 1<<30 | |
| #define endl '\n' | |
| #define maxn 100005 | |
| #define tc printf("Case %d: ", cs) | |
| #define tcn printf("Case %d:\n", cs); | |
| #define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); | |
| typedef long long ll; | |
| const double PI = acos(-1.0); | |
| #define dbg(x) cerr << #x << " = " << x << endl; | |
| #define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl; | |
| #define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl; | |
| #define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl; | |
| const int Mod = 100000007; | |
| int n, k; | |
| int coin[55], make[55]; | |
| int dp[55][1001]; | |
| int solve(int i, int amount) | |
| { | |
| if (i >= n) { | |
| if (amount == 0) return 1; | |
| else return 0; | |
| } | |
| if (dp[i][amount] != -1) return dp[i][amount]; | |
| int ret = 0; | |
| for (int t = 1; t <= make[i]; t++) { | |
| if (amount - (coin[i] * t) >= 0) | |
| ret += (solve(i + 1, amount - (coin[i] * t) )) % Mod; | |
| else break; | |
| } | |
| ret += (solve(i + 1, amount)) % Mod; | |
| return dp[i][amount] = ret % Mod; | |
| } | |
| int main() | |
| { | |
| //FASTIO | |
| ///* | |
| //double start_time = clock(); | |
| #ifndef ONLINE_JUDGE | |
| freopen("in.txt", "r", stdin); | |
| freopen("out.txt", "w", stdout); | |
| freopen("error.txt", "w", stderr); | |
| #endif | |
| //*/ | |
| int T; | |
| scanf("%d", &T); | |
| for (int cs = 1; cs <= T; cs++) { | |
| memset(dp, -1, sizeof dp); | |
| scanf("%d %d", &n, &k); | |
| for (int i = 0; i < n; i++) { | |
| scanf("%d", &coin[i]); | |
| } | |
| for (int i = 0; i < n; i++) { | |
| scanf("%d", &make[i]); | |
| } | |
| printf("Case %d: %d\n", cs, solve(0, k) % Mod); | |
| } | |
| //double end_time = clock(); | |
| //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000); | |
| return 0; | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| ///https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=615 | |
| /// O(NumberOfCoin * N) | |
| #include <bits/stdc++.h> | |
| using namespace std; | |
| #define INF 1<<30 | |
| #define endl '\n' | |
| #define maxn 100005 | |
| #define tc printf("Case %d: ", cs) | |
| #define tcn printf("Case %d:\n", cs); | |
| #define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); | |
| typedef long long ll; | |
| const double PI = acos(-1.0); | |
| #define dbg(x) cerr << #x << " = " << x << endl; | |
| #define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl; | |
| #define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl; | |
| #define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl; | |
| int coin[] = {1, 5, 10, 25, 50}; | |
| int n; | |
| ll dp[6][7500]; | |
| ll solve(int i, int amount) | |
| { | |
| if (i >= 5) { | |
| if (amount == 0) return 1; | |
| else return 0; | |
| } | |
| if (dp[i][amount] != -1) | |
| { | |
| //dbg2(i, amount); | |
| return dp[i][amount]; | |
| } | |
| int ret1 = 0, ret2 = 0; | |
| if (amount - coin[i] >= 0) ret1 = solve(i, amount - coin[i]); //take the coin | |
| ret2 = solve(i + 1, amount); // don't take | |
| return dp[i][amount] = ret1 + ret2; | |
| } | |
| int main() | |
| { | |
| //FASTIO | |
| ///* | |
| //double start_time = clock(); | |
| #ifndef ONLINE_JUDGE | |
| freopen("in.txt", "r", stdin); | |
| freopen("out.txt", "w", stdout); | |
| freopen("error.txt", "w", stderr); | |
| #endif | |
| //*/ | |
| memset(dp, -1, sizeof dp); | |
| while (scanf("%d", &n) != EOF) { | |
| //dbg(n); | |
| printf("%lld\n", solve(0, n)); | |
| } | |
| //double end_time = clock(); | |
| //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000); | |
| return 0; | |
| } |
No comments:
Post a Comment