管理人の独り言（プログラミング関連）

1532： ◆adhRKFl5jU：2009/03/01(日) 18:43:58: jid36
問題番号 9
点数 100
-----
/*
TASK: Nile.com
LANG: C++
NAME: Kazuhiro Hosaka JPN13
*/

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <algorithm>
#include <bitset>
#include <complex>

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
#define mp make_pair

template<class T> void pv(T a, T b) { for (T i=a; i!=b; ++i) cout << *i << " "; cout << endl; }
template<class T> void pvp(T a, T b) { for (T i=a; i!=b; ++i) cout << "(" << i->first << ", " << i->second << ") "; cout << endl; }

/*
dp state
i<<1 : * -> i -> now
i<<1|1 : i -> i -> now
N<<1 : * -> * -> now
*/

const int INF = 1001001001;

int N,D;
int A[370][3010];
int dp[2][6010],*dp0,*dp1;

int main() {
//freopen("nile.in", "r", stdin);

int i,j;

scanf("%i%i", &N, &D);
for (j=0; j<D; ++j) {
for (i=0; i<N; ++i) {
scanf("%i", &A[j][i]);
}
}

for (i=0; i<N; ++i) {
dp[0][i<<1] = dp[0][i<<1|1] = INF;
}
for (j=0; j<D; ++j) {
dp0 = dp[j&1], dp1 = dp[(j&1)^1];
dp1[N<<1] = INF;
for (i=0; i<N; ++i) {
dp1[i<<1] = dp0[N<<1] + A[j][i];
dp1[i<<1|1] = min(dp0[i<<1] + A[j][i] / 10 * 9, dp0[i<<1|1] + A[j][i] / 10 * 7);
dp1[N<<1] = min(dp1[N<<1], dp1[i<<1]);
dp1[N<<1] = min(dp1[N<<1], dp1[i<<1|1]);
}
}

printf("%i\n", dp[D&1][N<<1]);

return 0;
}

新着レスの表示

※書き込む際の注意事項はこちら

※画像アップローダーはこちら

（画像を表示できるのは「画像リンクのサムネイル表示」がオンの掲示板に限ります）

掲示板管理者へ連絡無料レンタル掲示板