JOI'08春2-1 Nile.com

JOI難易度6

問題概要

D日間,N個の店から1つ選んで商品を買う.2日連続だと1割引,3日以上連続だと3割引になる.
出費の最小値を求めよ.

解法

DP.
dp[i][j][k]=(i日目にjで買うのがk日連続)
とするとよい.連続しない場合の遷移がO(N)かかってしまうので前計算して高速化.MLE対策に日数をmod 2にすると通る.

ソースコード

めっちゃきたない

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define REPR(i,n) for(int i=(n);i>=0;i--)
#define all(vec) vec.begin(),vec.end()
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<ll,ll>;
using PP=pair<ll,P>;
using vp=vector<P>;
using vpp=vector<PP>;
using vs=vector<string>;
#define fi first
#define se second
#define pb push_back
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
const ll MOD=1000000007LL;
const int INF=1<<30;
const ll LINF=1LL<<60;
int main(){
    int n,d;
    cin>>n>>d;
    vvl vec(d,vl(n));
    REP(i,d){
        REP(j,n){
            cin>>vec[i][j];
        }
    }
    vector<vvl> dp(2,vvl(n,vl(3,LINF)));
    REP(i,n){
        dp[0][i][0]=vec[0][i];
    }
    FOR(i,1,d){
        vp m(2,P(LINF,0));
        REP(j,n){
            ll t=LINF;
            REP(k,3){
                chmin(t,dp[(i+1)%2][j][k]);
            }
            if(t<m[0].fi){
                m[1]=m[0];
                m[0]=P(t,j);
            }else if(t<m[1].fi){
                m[1]=P(t,j);
            }
        }
        REP(j,n){
            REP(k,3){
                dp[i%2][j][k]=LINF;
            }
        }
        REP(j,n){
            if(m[0].se==j){
                chmin(dp[i%2][j][0],m[1].fi+vec[i][j]);
            }else{
                chmin(dp[i%2][j][0],m[0].fi+vec[i][j]);
            }
            chmin(dp[i%2][j][1],dp[(i+1)%2][j][0]+vec[i][j]*9/10);
            chmin(dp[i%2][j][2],min(dp[(i+1)%2][j][1],dp[(i+1)%2][j][2])+vec[i][j]*7/10);
        }
    }
    ll ans=LINF;
    REP(i,n){
        REP(j,3){
            chmin(ans,dp[(d-1)%2][i][j]);
        }
    }
    cout<<ans<<endl;
    return 0;
}