Algoogle

Algorithm for Programming Contest

JOI 春合宿 2008 Nile.Com

Category: JOI Tag: dp

Nile.Com

問題概要


各店でi日目に買う商品の値段が決まっている.
2日連続で同じ店で購入すると1割引, 3日以上連続だと3割引で商品を買える.
最小のコストを求めよ

解法


DP
dp[\i][\j][\k] := i日目に店jで連続k回購入した時の最小のコスト
新しい店で買うときは前日までの最小のコストから遷移する(一区切りついて前の状態が関係なくなる).

コード


(Nile.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
const int g[] = {10,9,7};
int n, d, f[512][4096], dp[512][4096][4];

int solve()
{

        int m = 0, zero;
        for (int i = 0; i < d; i++) {
                zero = m;
                m = 1e9;
                for (int j = 0; j < n; j++){
                        dp[i+1][j][1] = zero+f[i][j];
                        m = min(m, dp[i+1][j][1]);
                        for (int k = 1; k < 3; k++) {
                                if(!dp[i][j][k]) continue;
                                int nk = min(k+1, 2);
                                if(dp[i+1][j][nk]) dp[i+1][j][nk] = min(dp[i+1][j][nk], dp[i][j][k]+f[i][j]/10*g[k]);
                                else dp[i+1][j][nk] = dp[i][j][k]+f[i][j]/10*g[k];
                                m = min(m, dp[i+1][j][nk]);
                        }
                }
        }

        return m;
}

void input()
{
        cin >> n >> d;
        for (int i = 0; i < d; i++)
                for (int j = 0; j < n; j++)
                        cin >> f[i][j];
}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        cout << solve() << endl;
        return 0;
}

Comments