PKU1032

PKU1032を解いている途中。
問題、N（5<=N<=1000)が与えられたとき、Nを異なるいくつかのグループに分割する（例えば、N=5の時、5=2+3のように)。このとき、分割したグループの積が最大となる分割の仕方の出力せよ。

解答を考える。DPっぽい感じがする。例えば、こんな感じ。

F[i,j] => i以上のグループでのjの分割した時のグループの積の最大値
F[i,0] = 1 (i>=0の時、分割していくとここに行きつく）
F[i,j] = 0 (i>jの時,このとき分割はできない）
F[i,j] = iからjの数で分割する。kをiからjの数とすると、部分問題は、F[k+1,j-k]となる。このkをiからjで動かした時のmax( i*F[k+1,j-k] )がこの値になる。

で、以下がこれをメモ化再帰でコード化したもの

#include<iostream>
#include<vector>
using namespace std;

double memo[1001][1001]={{-1}};
pair<int,int> record[1001][1001];

int memotan(int p,int rest){
  if(rest==0 )
    return 1;
  if(p>rest)
    return 0;
  if(memo[p][rest]!=-1)
    return memo[p][rest];
  double mx = -1;
  int ii;
  for(int i=p;i<=rest;i++){
    double temp = memotan(i+1,rest-i);
    if(mx < i*temp){
      mx = i*temp;
      ii=i;
    }
  }
  
  memo[p][rest]=ii;
  memo[p][rest]=mx;
  record[p][rest]=pair<int,int>(ii,rest);
  return memo[p][rest];
}
  
void output(int p,int rest){
  if(rest==0)
    return ;
  output(record[p][rest].first+1,
	 record[p][rest].second-record[p][rest].first);
  cout << record[p][rest].first << " ";
}

int main(){
  for(int i=0;i<1001;i++)
    for(int j=0;j<1001;j++)
      memo[i][j]=-1;
  memo[0][0]=1;
  
  int N;cin >>N;
  for(int i=0;i<N;i++){
    int c;
    cin >> c;
    cout << c << endl;
    memotan(2,c);
    output(2,c);
    cout << endl;
  }
  return 0;
}

と、このコードでは正しくない。桁あふれが発生しているから値が大きくなると死ぬ。
んー、どうするかと今考えているところ。小さい値で試すと、いくつか法則性が見つかるこれをコード化してみようと思う。
いくつか、小さい順に解を示していくと、

5 -> 2 3      -
6 -> 2 4      |  2つのグループは,4つ
7 -> 3 4      |  
8 -> 3 5      -
9 -> 2 3 4    -
10 -> 2 3 5   |　
11 -> 2 4 5   |　3つのグループは,5
12 -> 3 4 5   |
13 -> 3 4 6   -
14 -> 2 3 4 5 -
15 -> 2 3 4 6 |
16 -> 2 3 5 6 | 4つのグループは,6
17 -> 2 4 5 6 |
18 -> 3 4 5 6 |
19 -> 3 4 5 7 -

となる。さらに、各グループでは、1つ前のグループに、後ろから１づつ足していったもの。

例
14 -> 2 3 4 5
　　　　　　+1
15 -> 2 3 4 6
　　　　　+1  
16 -> 2 3 5 6

これを、単純に実装すると、

#include<iostream>
#include<vector>
using namespace std;

int group[1001]={0};

int main(){
  int k=5;
  //各数字がいくつの要素のグループかを先に書いておく
  for(int i=4;i<1001;i++){
    for(int j=0;j<i;j++){
      if(k+j>1000)
	break;
      group[k+j] = i-2;
    }
    k+=i;
  }
  int n;
  cin >> n;
  vector<int> ans;
  int sm = 0;
  //2から順に連続したgroup[n]個を答えに入れる。
  for(int i=0;i<group[n];i++){
    ans.push_back(i+2);
    sm += i+2;
  }
  int j=ans.size()-1;
  //答えの合計がn二届かない分後ろから1足していく
  while(sm<n){
    ans[j]++;
    sm+=1;
    j--;
    if(j==-1)
      j=ans.size()-1;
  }
  for(int i=0;i<ans.size();i++){
    cout << ans[i];
    if(i!=ans.size()-1)
      cout << " ";
  }
  return 0;
}

とこれで、やっとPKUでacceptされた。ふぅ