Algoogle

Algorithm for Programming Contest

AOJ 0120 Patiserie

Category: AOJ Tag: dp

Patisserie

問題概要


解法


すべてのロールケーキの順番を決めるのでbitDPする.
dp[i][j] := 集合iに含まれないものと最後にjを並べた時の最小
隣り合ったロールケーキの中心間の横幅は
これを2点間の辺の大きさと考えてbitDPすればいい.

コード


(0120.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
#include <iostream>
#include <cstdio>
#include <sstream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
#define rep(i,a) for(int i = 0; i < a; i++)
#define repd(i,a,b) for(int i = a; i > b; i--)
#define pb push_back
#define INF 10000000

int main(){
    string str;
    while(getline(cin,str)){
        vector<int> r;
        stringstream s(str);
        int n = 0, w;
        s >> w;
        while(!s.eof()){
            int t;
            s >> t;
            r.pb(t);
            n++;
        }
        vector<vector<double> > dp(1<<n,vector<double> (n,INF));
        rep(i,n) dp[(1<<n)-1-(1<<i)][i] = r[i];

        repd(i,(1<<n)-2,-1) rep(j,n){
            if(!(i&(1<<j))){
                rep(k,n) {
                    dp[i][j] = min(dp[i][j],dp[i|(1<<j)][k]+2*sqrt(r[j]*r[k]));
                }
            }
        }
        double ans = INF;
        rep(i,n) ans = min(ans,dp[0][i]+r[i]);
        cout << ((ans <= w)? "OK": "NA") << endl;
    }
}

Comments