ダイナミックプランニング法2/標準
62175 ワード
11066:ファイルのマージ
https://www.acmicpc.net/problem/11066
問題を解く
minCost[l][r]=l⋯rmCost[l][r]=lcdots rmCost[l][r]=l⋯rファイルのマージに必要な最小コスト
minCost[l][r]=mini=l⋯r−1(minCost[l][i]+minCost[i+1][r]+sum(l⋯r))minCost[l][r] =\underset{i = l\cdots r - 1}{min}(minCost[l][i] + minCost[i + 1][r] + sum_{(l\cdots r)})minCost[l][r]=i=l⋯r−1min(minCost[l][i]+minCost[i+1][r]+sum(l⋯r))
minCost[501][501]minCost[501]minCost[501][501]またはminCost[500][500]minCost[500]minCost[500]MinCost[500][500]または大きさに大きな差はなく、コードの便宜上、当初は電子的に書かれていたが、差の大きさはsizeof(int)×1001sizeof(int)\times 1001sizeof(int)×1001はずいぶん違います.
これから気をつけます.
これはKnuth's Optimizationに適用される問題です.
コード#コード#
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
int T, K, file[500], sum[500], minCost[500][500] = {0, };
scanf("%d", &T);
while(T--) {
scanf("%d", &K);
scanf("%d", &file[0]);
sum[0] = file[0];
for(int i = 1; i < K; i++) {
scanf("%d", &file[i]);
sum[i] = sum[i - 1] + file[i];
}
for(int gap = 1; gap < K; gap++)
for(int l = 0; l + gap < K; l++) {
int r = l + gap;
int &ret = minCost[l][r] = 987654321;
for(int i = l; i < r; i++)
ret = min(ret, minCost[l][i] + minCost[i + 1][r]);
ret += sum[r];
if(l > 0) ret -= sum[l - 1];
}
printf("%d\n", minCost[0][K - 1]);
}
}
11049回：行列乗算順
https://www.acmicpc.net/problem/11049
問題を解く
C[l][r]=l・rC[l][r]=lcdotsrC[l][r]=l・r行列への乗算回数の最大値
C[l][r]=mini=l⋯r−1(C[l][i]+C[i+1][r]+matrix[l].first∗matrix[i].second∗matrix[r].second)C[l][r] =\underset{i = l\cdots r - 1}{min}(C[l][i] + C[i + 1][r] + matrix[l].first * matrix[i].second * matrix[r].second)C[l][r]=i=l⋯r−1min(C[l][i]+C[i+1][r]+matrix[l].first∗matrix[i].second∗matrix[r].second)
コード#コード#
#include <cstdio>
#include <utility>
#include <algorithm>
using namespace std;
int main() {
int N, C[500][500] = {0, };
pair<int, int> matrix[500];
scanf("%d", &N);
for(int i = 0; i < N; i++)
scanf("%d %d", &matrix[i].first, &matrix[i].second);
for(int gap = 1; gap < N; gap++)
for(int l = 0; l + gap < N; l++) {
int r = l + gap;
int &ret = C[l][r] = (1 << 31) - 1;
for(int i = l; i < r; i++)
ret = min(ret, C[l][i] + C[i + 1][r] + matrix[l].first * matrix[i].second * matrix[r].second);
}
printf("%d", C[0][N - 1]);
}
1520号:下り坂
https://www.acmicpc.net/problem/1520
問題を解く
countPath(y,x)=[y,x]countPath(y,x)=[y,x]countPath(y,x)=[y,x]から[M21][M-1][M-1][M21][N21]までの経路数
[y 2,x 2][y 2,x 2][y 2,x 2][y 2,x 2]が[y,x][y,x][y,x][y,x]隣接x]の頂点であり、he[ y 2][x 2]コード#コード#
#include <cstdio>
#include <cstring>
int M, N, height[500][500], cache[500][500];
int d[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };
int countPath(int y, int x) {
if(y == M - 1 && x == N - 1) return 1;
int &ret = cache[y][x];
if(ret != -1) return ret;
ret = 0;
for(int i = 0; i < 4; i++) {
int y2 = y + d[i][0], x2 = x + d[i][1];
if(y2 < 0 || y2 >= M || x2 < 0 || x2 >= N) continue;
if(height[y][x] > height[y2][x2])
ret += countPath(y2, x2);
}
return ret;
}
int main() {
scanf("%d %d", &M, &N);
for(int i = 0; i < M; i++)
for(int j = 0; j < N; j++)
scanf("%d", &height[i][j]);
memset(cache, -1, sizeof(cache));
printf("%d", countPath(0, 0));
}
10942号:ファリン・ドロン?
https://www.acmicpc.net/problem/10942
問題を解く
isp[l][r]=num[l]isp[l][r]=num[lcdotsr]isp[l]=num[l][l]はファリンドロンですか?
isP[l][r]=isP[l+1][r−1] && (num[l]==num[r])isP[l][r] = isP[l + 1][r - 1]\\&\&\(num[l] == num[r])isP[l][r]=isP[l+1][r−1] && (num[l]==num[r])
コード#コード#
#include <cstdio>
int N, M, num[2000];
bool isP[2000][2000];
int main() {
scanf("%d", &N);
for(int i = 0; i < N; i++)
scanf("%d", &num[i]);
for(int i = 0; i < N; i++) isP[i][i] = true;
for(int i = 0; i < N - 1; i++) isP[i][i + 1] = (num[i] == num[i + 1]);
for(int gap = 2; gap < N; gap++)
for(int l = 0; l + gap < N; l++) {
int r = l + gap;
isP[l][r] = isP[l + 1][r - 1] && (num[l] == num[r]);
}
scanf("%d", &M);
int l, r;
for(int i = 0; i < M; i++) {
scanf("%d %d", &l, &r);
printf("%d\n", isP[l - 1][r - 1]);
}
}
2629号:両腕秤
https://www.acmicpc.net/problem/2629
問題を解く
canCheck(i,w)=weight[i]canCheck(i,w)=weight[icdots]canCheck(i,w)=weight[i]のプッシュでwの重量を確定できますか?
1. i1.\i1. i番ハンマーを使用しない場合
canCheck(i,w) ∣=canCheck(i+1,w)canCheck(i, w)\|= canCheck(i + 1, w)canCheck(i,w) ∣=canCheck(i+1,w)
2. i2.\i2. i番玉が反対側に置かれているとき
canCheck(i,w) ∣=canCheck(i+1,w−weight[i])canCheck(i, w)\|= canCheck(i + 1, w - weight[i])canCheck(i,w) ∣=canCheck(i+1,w−weight[i])
3. i3.\i3. i番玉が置いてあるとき
canCheck(i,w) ∣=canCheck(i+1,w+weight[i])canCheck(i, w)\|= canCheck(i + 1, w + weight[i])canCheck(i,w) ∣=canCheck(i+1,w+weight[i])
wの値はビーズ重量が1,30テーパ重量がいずれも500の場合の最小値は−14999であるため,cacheアレイに近づくと14999を加えた.
コード#コード#
#include <cstdio>
#include <cstring>
int weightNum, weight[30], marbleNum;
char cache[30][70000];
bool canCheck(int i, int w) {
if(i == weightNum) return (w == 0);
char &ret = cache[i][w + 14999];
if(ret != -1) return ret;
return ret = canCheck(i + 1, w) || canCheck(i + 1, w - weight[i]) || canCheck(i + 1, w + weight[i]);
}
int main() {
scanf("%d", &weightNum);
for(int i = 0; i < weightNum; i++)
scanf("%d", &weight[i]);
scanf("%d", &marbleNum);
memset(cache, -1, sizeof(cache));
for(int i = 0; i < marbleNum; i++) {
int marble; scanf("%d", &marble);
printf("%s ", canCheck(0, marble) ? "Y" : "N");
}
}
2293号:コイン1
https://www.acmicpc.net/problem/2293
問題を解く
cache[i][k]=1cdots icache[i][k]=1引用符iの硬貨を使用して値の和をkに充填したときの数
i個目の硬貨で充填しない
cache[i][k]=cache[i−1][k]cache[i][k] = cache[i - 1][k]cache[i][k]=cache[i−1][k] k>=硬貨[i]k>=硬貨[i]k>=硬貨[i]の場合、1個目iの1個目の硬貨を使用する
cache[i][k] +=cache[i][k−coin[i]]cache[i][k]\+= cache[i][k - coin[i]]cache[i][k] +=cache[i][k−coin[i]] 繰り返されるダイナミックプランニング法を作成する際には,スライドウィンドウ法を用いることができるかどうかを考慮しなければならない.
スライドウィンドウテクノロジーを使用する場合、キャッシュ配列の増大を考慮する必要がないため、1からインデックスを使用してベースインスタンスを処理する方法が容易に使用できます.
したがって,cache配列が大きくなるのを防止するために,基板インスタンスを複雑に記述する必要はないことを忘れないでください.
スライドウィンドウをアジェの1次元アレイに上書きする形で記述することもできます.
スライドウィンドウは、使用されなくなった値を破棄することで空間の複雑さを向上させる方法と見なされます.
コード#コード#
#include <cstdio>
int main() {
int n, k, coin[101], cache[2][10001] = {0, };
scanf("%d %d", &n, &k);
for(int i = 1; i <= n; i++)
scanf("%d", &coin[i]);
cache[0][0] = 1;
for(int i = 1; i <= n; i++) {
cache[i % 2][0] = 1;
for (int sum = 1; sum <= k; sum++) {
cache[i % 2][sum] = cache[(i - 1) % 2][sum];
if (sum >= coin[i])
cache[i % 2][sum] += cache[i % 2][sum - coin[i]];
}
}
printf("%d", cache[n % 2][k]);
}
// 1차원 배열 형태만으로 계산
#include <cstdio>
int main() {
int n, k, coin[101], cache[10001] = {1, };
scanf("%d %d", &n, &k);
for(int i = 1; i <= n; i++)
scanf("%d", &coin[i]);
for(int i = 1; i <= n; i++)
for (int sum = 1; sum <= k; sum++)
if (sum >= coin[i])
cache[sum] += cache[sum - coin[i]];
printf("%d", cache[k]);
}
7579:アプリケーション
https://www.acmicpc.net/problem/7579
問題を解く
dp[idx][cost]=1⋯idp[idx][cost]=1cdots idp[idx][cost]=1⋯iのアプリケーションがアプリケーションを無効にしたときの最大使用可能メモリ
idxアプリケーションが無効になっていない場合
dp[idx][cost]=dp[idx−1][cost]dp[idx][cost] = dp[idx - 1][cost]dp[idx][cost]=dp[idx−1][cost] idxアプリケーションを無効にした場合(コスト>=c[idx])
dp[idx][cost]=dp[idx−1][cost−c[idx]]+m[idx]dp[idx][cost] = dp[idx - 1][cost - c[idx]] + m[idx]dp[idx][cost]=dp[idx−1][cost−c[idx]]+m[idx] スライド窓技術を採用した.
コード#コード#
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
int N, M, m[101], c[101], dp[10001] = {0, }, costSum = 0;
scanf("%d %d", &N, &M);
for(int i = 1; i <= N; i++)
scanf("%d", &m[i]);
for(int i = 1; i <= N; i++) {
scanf("%d", &c[i]);
costSum += c[i];
}
for(int idx = 1; idx <= N; idx++)
for(int cost = costSum; cost >= 1; cost--)
if(cost >= c[idx])
dp[cost] = max(dp[cost], dp[cost - c[idx]] + m[idx]);
for(int cost = 1; cost <= costSum; cost++)
if(dp[cost] >= M) {
printf("%d", cost);
break;
}
return 0;
}
Reference
この問題について(ダイナミックプランニング法2/標準), 我々は、より多くの情報をここで見つけました
https://velog.io/@jhjjj/동적-계획법-2-백준
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
int T, K, file[500], sum[500], minCost[500][500] = {0, };
scanf("%d", &T);
while(T--) {
scanf("%d", &K);
scanf("%d", &file[0]);
sum[0] = file[0];
for(int i = 1; i < K; i++) {
scanf("%d", &file[i]);
sum[i] = sum[i - 1] + file[i];
}
for(int gap = 1; gap < K; gap++)
for(int l = 0; l + gap < K; l++) {
int r = l + gap;
int &ret = minCost[l][r] = 987654321;
for(int i = l; i < r; i++)
ret = min(ret, minCost[l][i] + minCost[i + 1][r]);
ret += sum[r];
if(l > 0) ret -= sum[l - 1];
}
printf("%d\n", minCost[0][K - 1]);
}
}https://www.acmicpc.net/problem/11049
問題を解く
C[l][r]=l・rC[l][r]=lcdotsrC[l][r]=l・r行列への乗算回数の最大値
C[l][r]=mini=l⋯r−1(C[l][i]+C[i+1][r]+matrix[l].first∗matrix[i].second∗matrix[r].second)C[l][r] =\underset{i = l\cdots r - 1}{min}(C[l][i] + C[i + 1][r] + matrix[l].first * matrix[i].second * matrix[r].second)C[l][r]=i=l⋯r−1min(C[l][i]+C[i+1][r]+matrix[l].first∗matrix[i].second∗matrix[r].second)
コード#コード#
#include <cstdio>
#include <utility>
#include <algorithm>
using namespace std;
int main() {
int N, C[500][500] = {0, };
pair<int, int> matrix[500];
scanf("%d", &N);
for(int i = 0; i < N; i++)
scanf("%d %d", &matrix[i].first, &matrix[i].second);
for(int gap = 1; gap < N; gap++)
for(int l = 0; l + gap < N; l++) {
int r = l + gap;
int &ret = C[l][r] = (1 << 31) - 1;
for(int i = l; i < r; i++)
ret = min(ret, C[l][i] + C[i + 1][r] + matrix[l].first * matrix[i].second * matrix[r].second);
}
printf("%d", C[0][N - 1]);
}1520号:下り坂
https://www.acmicpc.net/problem/1520
問題を解く
countPath(y,x)=[y,x]countPath(y,x)=[y,x]countPath(y,x)=[y,x]から[M21][M-1][M-1][M21][N21]までの経路数
[y 2,x 2][y 2,x 2][y 2,x 2][y 2,x 2]が[y,x][y,x][y,x][y,x]隣接x]の頂点であり、he[ y 2][x 2]コード#コード#
#include <cstdio>
#include <cstring>
int M, N, height[500][500], cache[500][500];
int d[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };
int countPath(int y, int x) {
if(y == M - 1 && x == N - 1) return 1;
int &ret = cache[y][x];
if(ret != -1) return ret;
ret = 0;
for(int i = 0; i < 4; i++) {
int y2 = y + d[i][0], x2 = x + d[i][1];
if(y2 < 0 || y2 >= M || x2 < 0 || x2 >= N) continue;
if(height[y][x] > height[y2][x2])
ret += countPath(y2, x2);
}
return ret;
}
int main() {
scanf("%d %d", &M, &N);
for(int i = 0; i < M; i++)
for(int j = 0; j < N; j++)
scanf("%d", &height[i][j]);
memset(cache, -1, sizeof(cache));
printf("%d", countPath(0, 0));
}
10942号:ファリン・ドロン?
https://www.acmicpc.net/problem/10942
問題を解く
isp[l][r]=num[l]isp[l][r]=num[lcdotsr]isp[l]=num[l][l]はファリンドロンですか?
isP[l][r]=isP[l+1][r−1] && (num[l]==num[r])isP[l][r] = isP[l + 1][r - 1]\\&\&\(num[l] == num[r])isP[l][r]=isP[l+1][r−1] && (num[l]==num[r])
コード#コード#
#include <cstdio>
int N, M, num[2000];
bool isP[2000][2000];
int main() {
scanf("%d", &N);
for(int i = 0; i < N; i++)
scanf("%d", &num[i]);
for(int i = 0; i < N; i++) isP[i][i] = true;
for(int i = 0; i < N - 1; i++) isP[i][i + 1] = (num[i] == num[i + 1]);
for(int gap = 2; gap < N; gap++)
for(int l = 0; l + gap < N; l++) {
int r = l + gap;
isP[l][r] = isP[l + 1][r - 1] && (num[l] == num[r]);
}
scanf("%d", &M);
int l, r;
for(int i = 0; i < M; i++) {
scanf("%d %d", &l, &r);
printf("%d\n", isP[l - 1][r - 1]);
}
}
2629号:両腕秤
https://www.acmicpc.net/problem/2629
問題を解く
canCheck(i,w)=weight[i]canCheck(i,w)=weight[icdots]canCheck(i,w)=weight[i]のプッシュでwの重量を確定できますか?
1. i1.\i1. i番ハンマーを使用しない場合
canCheck(i,w) ∣=canCheck(i+1,w)canCheck(i, w)\|= canCheck(i + 1, w)canCheck(i,w) ∣=canCheck(i+1,w)
2. i2.\i2. i番玉が反対側に置かれているとき
canCheck(i,w) ∣=canCheck(i+1,w−weight[i])canCheck(i, w)\|= canCheck(i + 1, w - weight[i])canCheck(i,w) ∣=canCheck(i+1,w−weight[i])
3. i3.\i3. i番玉が置いてあるとき
canCheck(i,w) ∣=canCheck(i+1,w+weight[i])canCheck(i, w)\|= canCheck(i + 1, w + weight[i])canCheck(i,w) ∣=canCheck(i+1,w+weight[i])
wの値はビーズ重量が1,30テーパ重量がいずれも500の場合の最小値は−14999であるため,cacheアレイに近づくと14999を加えた.
コード#コード#
#include <cstdio>
#include <cstring>
int weightNum, weight[30], marbleNum;
char cache[30][70000];
bool canCheck(int i, int w) {
if(i == weightNum) return (w == 0);
char &ret = cache[i][w + 14999];
if(ret != -1) return ret;
return ret = canCheck(i + 1, w) || canCheck(i + 1, w - weight[i]) || canCheck(i + 1, w + weight[i]);
}
int main() {
scanf("%d", &weightNum);
for(int i = 0; i < weightNum; i++)
scanf("%d", &weight[i]);
scanf("%d", &marbleNum);
memset(cache, -1, sizeof(cache));
for(int i = 0; i < marbleNum; i++) {
int marble; scanf("%d", &marble);
printf("%s ", canCheck(0, marble) ? "Y" : "N");
}
}
2293号:コイン1
https://www.acmicpc.net/problem/2293
問題を解く
cache[i][k]=1cdots icache[i][k]=1引用符iの硬貨を使用して値の和をkに充填したときの数
i個目の硬貨で充填しない
cache[i][k]=cache[i−1][k]cache[i][k] = cache[i - 1][k]cache[i][k]=cache[i−1][k] k>=硬貨[i]k>=硬貨[i]k>=硬貨[i]の場合、1個目iの1個目の硬貨を使用する
cache[i][k] +=cache[i][k−coin[i]]cache[i][k]\+= cache[i][k - coin[i]]cache[i][k] +=cache[i][k−coin[i]] 繰り返されるダイナミックプランニング法を作成する際には,スライドウィンドウ法を用いることができるかどうかを考慮しなければならない.
スライドウィンドウテクノロジーを使用する場合、キャッシュ配列の増大を考慮する必要がないため、1からインデックスを使用してベースインスタンスを処理する方法が容易に使用できます.
したがって,cache配列が大きくなるのを防止するために,基板インスタンスを複雑に記述する必要はないことを忘れないでください.
スライドウィンドウをアジェの1次元アレイに上書きする形で記述することもできます.
スライドウィンドウは、使用されなくなった値を破棄することで空間の複雑さを向上させる方法と見なされます.
コード#コード#
#include <cstdio>
int main() {
int n, k, coin[101], cache[2][10001] = {0, };
scanf("%d %d", &n, &k);
for(int i = 1; i <= n; i++)
scanf("%d", &coin[i]);
cache[0][0] = 1;
for(int i = 1; i <= n; i++) {
cache[i % 2][0] = 1;
for (int sum = 1; sum <= k; sum++) {
cache[i % 2][sum] = cache[(i - 1) % 2][sum];
if (sum >= coin[i])
cache[i % 2][sum] += cache[i % 2][sum - coin[i]];
}
}
printf("%d", cache[n % 2][k]);
}
// 1차원 배열 형태만으로 계산
#include <cstdio>
int main() {
int n, k, coin[101], cache[10001] = {1, };
scanf("%d %d", &n, &k);
for(int i = 1; i <= n; i++)
scanf("%d", &coin[i]);
for(int i = 1; i <= n; i++)
for (int sum = 1; sum <= k; sum++)
if (sum >= coin[i])
cache[sum] += cache[sum - coin[i]];
printf("%d", cache[k]);
}
7579:アプリケーション
https://www.acmicpc.net/problem/7579
問題を解く
dp[idx][cost]=1⋯idp[idx][cost]=1cdots idp[idx][cost]=1⋯iのアプリケーションがアプリケーションを無効にしたときの最大使用可能メモリ
idxアプリケーションが無効になっていない場合
dp[idx][cost]=dp[idx−1][cost]dp[idx][cost] = dp[idx - 1][cost]dp[idx][cost]=dp[idx−1][cost] idxアプリケーションを無効にした場合(コスト>=c[idx])
dp[idx][cost]=dp[idx−1][cost−c[idx]]+m[idx]dp[idx][cost] = dp[idx - 1][cost - c[idx]] + m[idx]dp[idx][cost]=dp[idx−1][cost−c[idx]]+m[idx] スライド窓技術を採用した.
コード#コード#
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
int N, M, m[101], c[101], dp[10001] = {0, }, costSum = 0;
scanf("%d %d", &N, &M);
for(int i = 1; i <= N; i++)
scanf("%d", &m[i]);
for(int i = 1; i <= N; i++) {
scanf("%d", &c[i]);
costSum += c[i];
}
for(int idx = 1; idx <= N; idx++)
for(int cost = costSum; cost >= 1; cost--)
if(cost >= c[idx])
dp[cost] = max(dp[cost], dp[cost - c[idx]] + m[idx]);
for(int cost = 1; cost <= costSum; cost++)
if(dp[cost] >= M) {
printf("%d", cost);
break;
}
return 0;
}
Reference
この問題について(ダイナミックプランニング法2/標準), 我々は、より多くの情報をここで見つけました
https://velog.io/@jhjjj/동적-계획법-2-백준
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
コード#コード#
#include <cstdio>
#include <cstring>
int M, N, height[500][500], cache[500][500];
int d[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };
int countPath(int y, int x) {
if(y == M - 1 && x == N - 1) return 1;
int &ret = cache[y][x];
if(ret != -1) return ret;
ret = 0;
for(int i = 0; i < 4; i++) {
int y2 = y + d[i][0], x2 = x + d[i][1];
if(y2 < 0 || y2 >= M || x2 < 0 || x2 >= N) continue;
if(height[y][x] > height[y2][x2])
ret += countPath(y2, x2);
}
return ret;
}
int main() {
scanf("%d %d", &M, &N);
for(int i = 0; i < M; i++)
for(int j = 0; j < N; j++)
scanf("%d", &height[i][j]);
memset(cache, -1, sizeof(cache));
printf("%d", countPath(0, 0));
}10942号:ファリン・ドロン?
https://www.acmicpc.net/problem/10942
問題を解く
isp[l][r]=num[l]isp[l][r]=num[lcdotsr]isp[l]=num[l][l]はファリンドロンですか?
isP[l][r]=isP[l+1][r−1] && (num[l]==num[r])isP[l][r] = isP[l + 1][r - 1]\\&\&\(num[l] == num[r])isP[l][r]=isP[l+1][r−1] && (num[l]==num[r])
コード#コード#
#include <cstdio>
int N, M, num[2000];
bool isP[2000][2000];
int main() {
scanf("%d", &N);
for(int i = 0; i < N; i++)
scanf("%d", &num[i]);
for(int i = 0; i < N; i++) isP[i][i] = true;
for(int i = 0; i < N - 1; i++) isP[i][i + 1] = (num[i] == num[i + 1]);
for(int gap = 2; gap < N; gap++)
for(int l = 0; l + gap < N; l++) {
int r = l + gap;
isP[l][r] = isP[l + 1][r - 1] && (num[l] == num[r]);
}
scanf("%d", &M);
int l, r;
for(int i = 0; i < M; i++) {
scanf("%d %d", &l, &r);
printf("%d\n", isP[l - 1][r - 1]);
}
}
2629号:両腕秤
https://www.acmicpc.net/problem/2629
問題を解く
canCheck(i,w)=weight[i]canCheck(i,w)=weight[icdots]canCheck(i,w)=weight[i]のプッシュでwの重量を確定できますか?
1. i1.\i1. i番ハンマーを使用しない場合
canCheck(i,w) ∣=canCheck(i+1,w)canCheck(i, w)\|= canCheck(i + 1, w)canCheck(i,w) ∣=canCheck(i+1,w)
2. i2.\i2. i番玉が反対側に置かれているとき
canCheck(i,w) ∣=canCheck(i+1,w−weight[i])canCheck(i, w)\|= canCheck(i + 1, w - weight[i])canCheck(i,w) ∣=canCheck(i+1,w−weight[i])
3. i3.\i3. i番玉が置いてあるとき
canCheck(i,w) ∣=canCheck(i+1,w+weight[i])canCheck(i, w)\|= canCheck(i + 1, w + weight[i])canCheck(i,w) ∣=canCheck(i+1,w+weight[i])
wの値はビーズ重量が1,30テーパ重量がいずれも500の場合の最小値は−14999であるため,cacheアレイに近づくと14999を加えた.
コード#コード#
#include <cstdio>
#include <cstring>
int weightNum, weight[30], marbleNum;
char cache[30][70000];
bool canCheck(int i, int w) {
if(i == weightNum) return (w == 0);
char &ret = cache[i][w + 14999];
if(ret != -1) return ret;
return ret = canCheck(i + 1, w) || canCheck(i + 1, w - weight[i]) || canCheck(i + 1, w + weight[i]);
}
int main() {
scanf("%d", &weightNum);
for(int i = 0; i < weightNum; i++)
scanf("%d", &weight[i]);
scanf("%d", &marbleNum);
memset(cache, -1, sizeof(cache));
for(int i = 0; i < marbleNum; i++) {
int marble; scanf("%d", &marble);
printf("%s ", canCheck(0, marble) ? "Y" : "N");
}
}
2293号:コイン1
https://www.acmicpc.net/problem/2293
問題を解く
cache[i][k]=1cdots icache[i][k]=1引用符iの硬貨を使用して値の和をkに充填したときの数
#include <cstdio>
int N, M, num[2000];
bool isP[2000][2000];
int main() {
scanf("%d", &N);
for(int i = 0; i < N; i++)
scanf("%d", &num[i]);
for(int i = 0; i < N; i++) isP[i][i] = true;
for(int i = 0; i < N - 1; i++) isP[i][i + 1] = (num[i] == num[i + 1]);
for(int gap = 2; gap < N; gap++)
for(int l = 0; l + gap < N; l++) {
int r = l + gap;
isP[l][r] = isP[l + 1][r - 1] && (num[l] == num[r]);
}
scanf("%d", &M);
int l, r;
for(int i = 0; i < M; i++) {
scanf("%d %d", &l, &r);
printf("%d\n", isP[l - 1][r - 1]);
}
}https://www.acmicpc.net/problem/2629
問題を解く
canCheck(i,w)=weight[i]canCheck(i,w)=weight[icdots]canCheck(i,w)=weight[i]のプッシュでwの重量を確定できますか?
1. i1.\i1. i番ハンマーを使用しない場合
canCheck(i,w) ∣=canCheck(i+1,w)canCheck(i, w)\|= canCheck(i + 1, w)canCheck(i,w) ∣=canCheck(i+1,w)
2. i2.\i2. i番玉が反対側に置かれているとき
canCheck(i,w) ∣=canCheck(i+1,w−weight[i])canCheck(i, w)\|= canCheck(i + 1, w - weight[i])canCheck(i,w) ∣=canCheck(i+1,w−weight[i])
3. i3.\i3. i番玉が置いてあるとき
canCheck(i,w) ∣=canCheck(i+1,w+weight[i])canCheck(i, w)\|= canCheck(i + 1, w + weight[i])canCheck(i,w) ∣=canCheck(i+1,w+weight[i])
wの値はビーズ重量が1,30テーパ重量がいずれも500の場合の最小値は−14999であるため,cacheアレイに近づくと14999を加えた.
コード#コード#
#include <cstdio>
#include <cstring>
int weightNum, weight[30], marbleNum;
char cache[30][70000];
bool canCheck(int i, int w) {
if(i == weightNum) return (w == 0);
char &ret = cache[i][w + 14999];
if(ret != -1) return ret;
return ret = canCheck(i + 1, w) || canCheck(i + 1, w - weight[i]) || canCheck(i + 1, w + weight[i]);
}
int main() {
scanf("%d", &weightNum);
for(int i = 0; i < weightNum; i++)
scanf("%d", &weight[i]);
scanf("%d", &marbleNum);
memset(cache, -1, sizeof(cache));
for(int i = 0; i < marbleNum; i++) {
int marble; scanf("%d", &marble);
printf("%s ", canCheck(0, marble) ? "Y" : "N");
}
}2293号:コイン1
https://www.acmicpc.net/problem/2293
問題を解く
cache[i][k]=1cdots icache[i][k]=1引用符iの硬貨を使用して値の和をkに充填したときの数
cache[i][k]=cache[i−1][k]cache[i][k] = cache[i - 1][k]cache[i][k]=cache[i−1][k]
cache[i][k] +=cache[i][k−coin[i]]cache[i][k]\+= cache[i][k - coin[i]]cache[i][k] +=cache[i][k−coin[i]]
スライドウィンドウテクノロジーを使用する場合、キャッシュ配列の増大を考慮する必要がないため、1からインデックスを使用してベースインスタンスを処理する方法が容易に使用できます.
したがって,cache配列が大きくなるのを防止するために,基板インスタンスを複雑に記述する必要はないことを忘れないでください.
スライドウィンドウをアジェの1次元アレイに上書きする形で記述することもできます.
スライドウィンドウは、使用されなくなった値を破棄することで空間の複雑さを向上させる方法と見なされます.
コード#コード#
#include <cstdio>
int main() {
int n, k, coin[101], cache[2][10001] = {0, };
scanf("%d %d", &n, &k);
for(int i = 1; i <= n; i++)
scanf("%d", &coin[i]);
cache[0][0] = 1;
for(int i = 1; i <= n; i++) {
cache[i % 2][0] = 1;
for (int sum = 1; sum <= k; sum++) {
cache[i % 2][sum] = cache[(i - 1) % 2][sum];
if (sum >= coin[i])
cache[i % 2][sum] += cache[i % 2][sum - coin[i]];
}
}
printf("%d", cache[n % 2][k]);
}
// 1차원 배열 형태만으로 계산
#include <cstdio>
int main() {
int n, k, coin[101], cache[10001] = {1, };
scanf("%d %d", &n, &k);
for(int i = 1; i <= n; i++)
scanf("%d", &coin[i]);
for(int i = 1; i <= n; i++)
for (int sum = 1; sum <= k; sum++)
if (sum >= coin[i])
cache[sum] += cache[sum - coin[i]];
printf("%d", cache[k]);
}
7579:アプリケーション
https://www.acmicpc.net/problem/7579
問題を解く
dp[idx][cost]=1⋯idp[idx][cost]=1cdots idp[idx][cost]=1⋯iのアプリケーションがアプリケーションを無効にしたときの最大使用可能メモリ
dp[idx][cost]=dp[idx−1][cost]dp[idx][cost] = dp[idx - 1][cost]dp[idx][cost]=dp[idx−1][cost]
dp[idx][cost]=dp[idx−1][cost−c[idx]]+m[idx]dp[idx][cost] = dp[idx - 1][cost - c[idx]] + m[idx]dp[idx][cost]=dp[idx−1][cost−c[idx]]+m[idx]
コード#コード#
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
int N, M, m[101], c[101], dp[10001] = {0, }, costSum = 0;
scanf("%d %d", &N, &M);
for(int i = 1; i <= N; i++)
scanf("%d", &m[i]);
for(int i = 1; i <= N; i++) {
scanf("%d", &c[i]);
costSum += c[i];
}
for(int idx = 1; idx <= N; idx++)
for(int cost = costSum; cost >= 1; cost--)
if(cost >= c[idx])
dp[cost] = max(dp[cost], dp[cost - c[idx]] + m[idx]);
for(int cost = 1; cost <= costSum; cost++)
if(dp[cost] >= M) {
printf("%d", cost);
break;
}
return 0;
}Reference
この問題について(ダイナミックプランニング法2/標準), 我々は、より多くの情報をここで見つけました https://velog.io/@jhjjj/동적-계획법-2-백준テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol