Combinatorial - 0-1 Knapsack Problem
ナップザック問題 | 動的計画法 | Aizu Online Judge
シンプルなナップザック問題。
int main() {
int N, W; cin >> N >> W;
int v[105], w[105];
for (int i = 0; i < N; i++) cin >> v[i] >> w[i];
int dp[105][10005];
memset(dp, -1, sizeof(dp));
int res = 0;
dp[0][0] = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j <= W; j++) {
int k = j - w[i];
if (k >= 0 && dp[i][k] >= 0) {
dp[i + 1][j] = max(dp[i][j], dp[i][k] + v[i]);
} else {
dp[i + 1][j] = dp[i][j];
}
res = max(res, dp[i + 1][j]);
}
}
printf("%d\n", res);
return 0;
}
コイン問題 | 動的計画法 | Aizu Online Judge
コイン問題 | 動的計画法 | Aizu Online Judge
DPコースなるものを発見したので解いていこうと思う。
貪欲法でいける？と思ったが、コインの額面が半端なのでDPで解いていく。
int main() {
int n, m; cin >> n >> m;
int coins[25];
int dp[25][50005];
for (int i = 0; i < m; i++) cin >> coins[i];
for (int i = 0; i < 25; i++) fill(dp[i], dp[i] + 50005, 1000*1000);
dp[0][0] = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j <= n; j++) {
dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
int k = j - coins[i];
if (k >= 0) {
dp[i + 1][j] = min(dp[i + 1][j], dp[i][k] + 1);
dp[i + 1][j] = min(dp[i + 1][j], dp[i + 1][k] + 1);
}
}
}
printf("%d\n", dp[m][n]);
return 0;
}
0537: Bingo | Aizu Online Judge
状態数をうまく削減しないといけない。
int N, M, S;
int dp[50][3005];
int mod = 100000;
int main() {
while (1) {
cin >> N >> M >> S;
if (N == 0) break;
memset(dp, 0, sizeof(dp));
N *= N;
dp[0][0] = 1;
for (int i = 1; i <= M; i++) {
for (int j = N; j>0; j--){
for(int k=i;k<=S;k++){
dp[j][k]=(dp[j][k]+dp[j-1][k-i])%mod;
}
}
}
printf("%d\n", dp[N][S]);
}
return 0;
}
POJ 2441 : Arrange the Bulls
通ったんだけどこれでいいのかな。。
int N, M;
int cows[30][30] = {};
int memo[(1 << 20) + 1] = {};
int solve(int i, int S) {
if (memo[S] != -1) {
return memo[S];
}
if (i == N) return 1;
int res = 0;
for (int j = 0; j < M; j++) {
if (cows[i][j] && !(S & (1 << j))) {
res += solve(i+1, S | (1 << j));
}
}
return memo[S] = res;
}
int main() {
memset(memo, -1, sizeof(memo));
cin >> N >> M;
for (int i = 0; i < N; i++) {
int t;
cin >> t;
for (int j = 0; j < t; j++) {
int t2;
cin >> t2;
t2--;
cows[i][t2] = 1;
}
}
cout << solve(0, 0) << endl;
return 0;
}
Block | Aizu Online Judge
特に難しいことはないけど、入力ケースが多いので少しめんどくさい。
int mp[105][105];
bool visited[105][105];
int w, h;
int xs, ys;
int xg, yg;
int n;
int col;
int dx[]={-1,1,0,0};
int dy[]={0,0,1,-1};
void solve(int x, int y) {
visited[x][y]=1;
if (x==xg&&y==yg) return;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx<1 || nx > w || ny < 1 || ny > h) continue;
if (visited[nx][ny]) continue;
solve(nx, ny);
}
}
int main() {
while (1) {
memset(mp, 0, sizeof(mp));
memset(visited, 0, sizeof(visited));
cin >> w >> h;
if (w==0&&h==0) break;
cin >> xs >> ys;
cin >> xg >> yg;
cin >> n;
for (int i = 0; i < n; i++) {
int c, d, x, y; cin >> c >> d >> x >> y;
int jl, kl;
if (d==0)
jl = 4, kl = 2;
else
jl = 2; kl = 4;
for (int j = 0; j < jl; j++)
for (int k = 0; k < kl; k++)
mp[x+j][y+k]=c;
}
col = mp[xs][ys];
if (col != mp[xg][yg] || !col){
cout << "NG" << endl;
continue;
}
for (int i = 1; i <= w; i++) {
for (int j = 1; j <= h; j++){
if (mp[i][j] != col){
visited[i][j]=1;
}
}
}
solve(xs, ys);
if (visited[xg][yg]) {
cout << "OK" << endl;
} else {
cout << "NG" << endl;
}
}
return 0;
}
The Number of Island
教科書的なDFSの問題なんだが、入力ケースの終わりがちょっと特殊だった。 Patisserie | Aizu Online Judgeを彷彿とさせる。。
bool visited[13][13];
string mp[13];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
void solve(int x, int y) {
visited[x][y]=1;
for (int i =0; i < 4;i++) {
int nx=x+dx[i], ny=y+dy[i];
if (0<=nx&&nx<12&&0<=ny&&ny<12) {
if (!visited[nx][ny]){
solve(nx, ny);
}
}
}
}
int main() {
while (1) {
string s;
for (int i=0;i<4;i++){
getline(cin, s);
if (s!="")break;
}
if (s=="")break;
mp[0]=s;
for(int i = 0; i < 11; i++) cin >> mp[i+1];
memset(visited, 0, sizeof(visited));
for (int i = 0; i < 12; i++) {
for (int j = 0; j < 12; j++) {
if (mp[i][j]=='0') {
visited[i][j]=1;
}
}
}
int res=0;
for(int i=0;i<12;i++) {
for(int j=0;j<12;j++) {
if (visited[i][j])continue;
if (mp[i][j]=='1'){
solve(i, j);
res++;
}
}
}
cout << res << endl;
}
return 0;
}
Sum of Integers
こちらも玉に引き続き、シンプルに全通り試してみる。
int n, s;
int solve(int now, int left, int sum) {
if (left == 0) {
return sum == s;
}
if (now > 9) return 0;
int res = 0;
res+=solve(now+1, left-1, sum+now);
res+=solve(now+1, left, sum);
return res;
}
int main() {
while (1) {
cin >> n >> s;
if (n==0&&s==0)break;
cout << solve(0, n, 0) << endl;
}
return 0;
}
