AOJ0120
問題:Patisserie
DP難しい。
DPわけわからん。
#include<iostream> #include<string> #include<sstream> #include<vector> #include<cmath> using namespace std; int main() { string s; while(getline(cin,s), !s.empty()) { stringstream ss(s); int W; ss >> W; vector<int> R; int r; while(ss >> r) R.push_back(r); int N = R.size(); vector<vector<double> > dp(1<<N, vector<double>(N,10000000)); for(int i=0;i<N; ++i) dp[1<<i][i] = double(R[i]); for(int v=0; v<(1<<N); ++v) for(int i=0; i<N; ++i) for(int j=0; j<N; ++j) { if(v&(1<<j))continue; dp[v|(1<<j)][j] = min(dp[v|(1<<j)][j], dp[v][i] + sqrt(4*R[i]*R[j])); } double m_len = 10000000; for(int i=0; i<N; ++i) m_len = min(m_len, dp[(1<<N)-1][i] + double(R[i])); cout << ((m_len <= W) ? "OK" : "NA") << endl; } return 0; }
2013/02/03追加
メモ化再帰でも解いた。
#include<iostream> #include<cmath> #include<vector> #include<cstring> #include<sstream> using namespace std; vector<int> R; int N; double memo[1<<12][12]; double dfs(int v, int k) { if(memo[v][k] > 0)return memo[v][k]; if(v == (1<<N)-1) return R[k]; double mlen = 1<<20; for(int i=0;i<N;++i) { if(v&(1<<i))continue; if(v) mlen = min(mlen, dfs(v|(1<<i),i) + sqrt(4*R[i]*R[k])); else mlen = min(mlen, dfs(1<<i,i) + R[i]); } return memo[v][k] = mlen; } int main() { string s; while(getline(cin,s), !s.empty()) { memset(memo,-1,sizeof(memo)); stringstream ss(s); int W; ss >> W; int r; R.clear(); while(ss >> r) R.push_back(r); N = R.size(); if(dfs(0,0) <= W) cout << "OK" << endl; else cout << "NA" << endl; } }