Domains
K-Dimensional Foil
Graph
Chinese Checkers
Cats and Fish
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<vector> #include<algorithm> using std::vector; using std::sort; int cmp(const void * x, const void * y) { //x < y #define datatype int return (*((datatype *)(x))) > (*((datatype *)(y))) ? 1 : -1; #undef datatype } int v[105], a[1005][105], p[1005], s[105]; int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); #endif int m, n, x; while (scanf("%d%d%d", &m, &n, &x) != EOF) { for (int i = 0; i < n; i++) scanf("%d", &v[i]); memset(a, 0, sizeof(a)); memset(p, 0, sizeof(p)); for (int i = 0; i < n; i++) s[i] = -1000000; for (int i = 0; i < n; i++) { for (int j = 0; j <= x; j += v[i]) { a[j][p[j]++] = i; } } for (int i = 0; i <= x; i++) { if (m == 0) break; if (m >= p[i]) { for (int j = 0; j < p[i]; j++) { s[a[i][j]] = i; } m -= p[i]; } else { for (int ii = 0; ii < p[i]; ii++) { for (int jj = ii + 1; jj < p[i]; jj++) { if (v[a[i][ii]] > v[a[i][jj]]) { int tmp = a[i][ii]; a[i][ii] = a[i][jj]; a[i][jj] = tmp; } } } for (int j = 0; j < m; j++) { s[a[i][j]] = i; } m = 0; } } int com = m, incom = 0; for (int i = 0; i < n; i++) { int t = x - s[i]; if (t == 0) com++; else if (t >= v[i]) continue; else incom++; } printf("%d %d ", com, incom); } return 0; }
Secret Poems
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<vector> #include<algorithm> using std::vector; using std::sort; int cmp(const void * x, const void * y) { //x < y #define datatype int return (*((datatype *)(x))) > (*((datatype *)(y))) ? 1 : -1; #undef datatype } char poem[105][105], str[10005]; const int dx[4] = {0, 1, 0, -1}; const int dy[4] = {1, 0, -1, 0}; int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); #endif int n; while (scanf("%d", &n) != EOF) { for (int i = 0; i < n; i++) scanf("%s", poem[i]); int ptr = 0, dir = 1, x = 0, y = 0, p = 1; char tmp[500]; for (int i = 0; i < 2 * n - 1; i++) { int xx = x, yy = y; for (int j = 0; j < p; j++) { tmp[j] = poem[xx][yy]; xx--, yy++; } if (dir == 1) { for (int j = 0; j < p; j++) { str[ptr++] = tmp[j]; } } else { for (int j = p - 1; j >= 0; j--) { str[ptr++] = tmp[j]; } } dir *= -1; if (x + 1 < n) { x++; p++; } else { y++; p--; } } memset(poem, ' ', sizeof(poem)); for (int i = 0; i < n; i++) poem[i][n] = ' '; x = y = ptr = dir = 0; for (int i = 0; i < n * n; i++) { poem[x][y] = str[ptr++]; while (!((x + dx[dir] >= 0 && x + dx[dir] < n) && (y + dy[dir] >= 0 && y + dy[dir] < n) && (poem[x + dx[dir]][y + dy[dir]] == ' '))) { dir = (dir + 1) % 4; if (i + 1 == n * n) break; } x = x + dx[dir], y = y + dy[dir]; } for (int i = 0; i < n; i++) printf("%s ", poem[i]); } return 0; }
Liaoning Ship's Voyage
Puzzle Game
Colored Nodes
Pangu and Stones
动态规划：dp[i][j][k]表示从第i堆到第j堆进行若干次操作变成了k堆的最小花费，目标为dp[1][n][1]。
dp全部初始化为0x3F。
边界条件：
1.无操作：dp[i][j][j-i+1]=0
2.1次操作:dp[i][j][k]=sum(i,j) j-i+1∈[l,r]
转移方程：
dp[i][j][k]=min{dp[i][p][k-1]+dp[p+1][j][1]} k>1
dp[i][j][1]=min{dp[i][j][k]}+sum(i,j) k∈[l,r]
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<vector> #include<algorithm> using std::vector; using std::sort; int cmp(const void * x, const void * y) { //x < y #define datatype int return (*((datatype *)(x))) > (*((datatype *)(y))) ? 1 : -1; #undef datatype } int a[105], dp[105][105][105], sum[105]; int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); #endif int n, l, r; while (scanf("%d%d%d", &n, &l, &r) != EOF) { for (int i = 0; i < n; i++) scanf("%d", &a[i]); sum[0] = a[0]; for (int i = 1; i < n; i++) sum[i] = sum[i - 1] + a[i]; memset(dp, 0x3F, sizeof(dp)); for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { dp[i][j][j - i + 1] = 0; if (l <= j - i + 1 && j - i + 1 <= r) { dp[i][j][1] = sum[j] - sum[i] + a[i]; } } } /* dp[i][j][k]=min{dp[i][p][k-1]+dp[p+1][j][1]} */ for (int i = n - 1; i >= 0; i--) { for (int j = i; j < n; j++) { for (int k = 2; k <= j - i; k++) { for (int p = i; p < j; p++) { if (dp[i][j][k] > dp[i][p][k - 1] + dp[p + 1][j][1]) dp[i][j][k] = dp[i][p][k - 1] + dp[p + 1][j][1]; } } for (int k = l; k <= r; k++) { if (dp[i][j][1] > dp[i][j][k] + sum[j] - sum[i] + a[i]) dp[i][j][1] = dp[i][j][k] + sum[j] - sum[i] + a[i]; } } } if (dp[0][n - 1][1] == 0x3F3F3F3F) printf("0 "); else printf("%d ", dp[0][n - 1][1]); } return 0; }