2016-02-16

AOJ0611 - Silk Road (DP)

AOJ

AOJ0611のSilk RoadをDPの練習として解いてみました．
また，この問題を解くにあたって以下のサイトを参考にしました．

コード

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
 
#define MAX_D (1000)
#define MAX_C (1000)
 
int N, M;
int D[MAX_D], C[MAX_C];
// -1ならまだ調べていない
int dp[MAX_D + 1][MAX_C + 1];
 
int rec_dp(int now, int day);
 
int main()
{
  scanf("%d%d", &N, &M);
  memset(dp, -1, sizeof(dp)); // -1でメモ化テーブルを初期化
 
  for (int i = 0; i < N; i++) scanf("%d", &D[i]);
  for (int i = 0; i < M; i++) scanf("%d", &C[i]);
 
  printf("%d\n", rec_dp(0, 0));
 
  return (0);
}

// nowは現在地，dayは何日目かを表す
int rec_dp(int now, int day)
{
  if (dp[now][day] != -1){ // 一度調べていたら再利用
    return (dp[now][day]);
  }
   
  int res;
  if (now == N){ // 目的地に到着
    res = 0;
  }
  else if (N - now == M - day){ // 目的地に到着するためには進むしかない場合
    res = rec_dp(now + 1, day + 1) + (D[now] * C[day]);
  }
  else { // 進むか待機するか決められる場合
    res = min(rec_dp(now, day + 1), rec_dp(now + 1, day + 1) + (D[now] * C[day]));
  }
 
  dp[now][day] = res; // 結果を保存
 
  return (dp[now][day]);
}

提出したやつ

今回はメモ化再帰のDPで解きました．
またmemsetを初めて使ってみました．(31行目がdp[now][day] != 0でもいけそう)
単純な再帰に手を加えると計算効率がだいぶ上がるので，マスター出来るようにしたい．
また，漸化式を用いたDPも出来るようになりたい．(forだけで書けるので見た目もタイプ量も減りそう)
もっとこここうした方がいいよ，などあればコメント等に書いて頂ければ幸いです．

(この記事はictechの「Markdown超入門」を受け，Markdownで書かれています)

2016-01-30

AOJのsolve数が100問超えたよ!!やったね!!

AOJ 日記

ﾔｯﾀ-100solveｺｴﾀ-

こんにちは．kurokojiです．
やっとAOJで100solve超えました．年度内に100solveすることは目標にしてあったので達成することが出来たので良かったです．
次は200問ですね．

なんか100問解いた後，暇だったので

長方形 | プログラミング入門 | Aizu Online Judge
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1654385&tab=1

main(){int a,b;scanf("%d%d",&a,&b);printf("%d %d\n",a*b,2*a+2*b);return 0;}

なんだこれは!?

以上です．

2016-01-16

AOJ0005 - GCD and LCM (再帰)

AOJ

再帰分からないマンなので，今後に活かせるよう記事にして残しておきたいと思います．

最大公約数と最小公倍数 | Aizu Online Judge

この問題は入力された整数a, bの最大公約数と最小公倍数を求めるものです．
ユークリッドの互除法を使うことによって答えが出せます．
普通にwhile文とか使っても解けるのですが，今回は再帰で解きました．

AIZU ONLINE JUDGE: Code Review

#include <iostream>
using namespace std;

int gcd(int a, int b);

int main()
{
	int a, b;

	while (cin >> a >> b, cin.eof() != true){
		cout << gcd(a, b) << " " << a / gcd(a, b) * b << endl;
	}

	return (0);
}

int gcd(int a, int b)
{
	if (b == 0){
		return (a);
	}
	else {
		return (gcd(b, a % b));
	}
}