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;
  }
}