Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1814-f47f8cbe
この記事にトラックバックする(FC2ブログユーザー)

January 2011 Challenge 5問目 - Restaurant Expansion (この記事を編集する[管理者用])

Source

codechef January 2011 Challenge 5問目
Problem Statement
January 2011 Challengeの参加記録

問題概要

Nノード (30以下) の木が与えられる.
最初はノード1にシェフがC人 (30以下) いる.
各ノードに店を建てた場合の収益 (-1000以上1000以下) が与えられる.
各日に出来る行動は以下のとおり
 ・なにもしない
 ・シェフのいる場所,かつまだ店の建ててないノードに店を建てる
 ・店の建ててないノードのシェフを隣接するあるノードに移動させる.一度に何人でも移動できるが,移動先は同じ場所
D日間 (30以下) で収益を最大化する方法と最大値を求める問題.

解法

木の上でDPする.
今どこのノードにいて,シェフが何人いて,このサブツリーで費やせる日数を状態とする.
経路復元までしないといけないので実装は多少面倒.

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int N, C, D;
int dp[31][31][31][31];
int edge[31][31], es[31];
int gain[31];

int solve(int node, int chef, int day, int st, int up){
  int i,j,k,res=0;
  int next_node,tmp;

  if(dp[node][chef][day][st] >= 0) return dp[node][chef][day][st];

  if(st==es[node]){
    if(chef && day && gain[node] > 0) res += gain[node];
    return dp[node][chef][day][st] = res;
  }

  res = solve(node,chef,day,st+1,up);
  if(edge[node][st] != up){
    next_node = edge[node][st];
    rep(i,chef+1) REP(j,1,day+1){
      tmp = solve(next_node, i, j-1, 0, node) + solve(node, chef-i, day-j, st+1, up);
      if(tmp > res) res = tmp;
    }
  }

  return dp[node][chef][day][st] = res;
}

void output(int node, int chef, int day, int st, int up){
  int i,j,k,res=solve(node,chef,day,st,up);
  int next_node,tmp;

  if(st==es[node]){
    if(chef && day && gain[node] > 0){ printf("build %d\n",node+1); day--; }
    while(day--) puts("nothing");
    return;
  }

  tmp = solve(node,chef,day,st+1,up);
  if(res==tmp){
    output(node,chef,day,st+1,up);
    return;
  }
  
  if(edge[node][st] != up){
    next_node = edge[node][st];
    REP(i,1,chef+1) REP(j,1,day+1){
      tmp = solve(next_node, i, j-1, 0, node) + solve(node, chef-i, day-j, st+1, up);
      if(tmp == res){
        printf("transfer %d %d %d\n",node+1,next_node+1,i);
        output(next_node, i, j-1, 0, node);
        output(node, chef-i, day-j, st+1, up);
        return;
      }
    }
  }

}

int main(){
  int i,j,k,l,m;

  scanf("%d%d%d",&N,&C,&D);
  rep(i,N) scanf("%d",gain+i);
  rep(i,N) es[i]=0;
  REP(k,1,N){
    scanf("%d%d",&i,&j); i--; j--;
    edge[i][es[i]++]=j;
    edge[j][es[j]++]=i;
  }

  rep(i,N) rep(j,C+1) rep(k,D+1) rep(m,N+1) dp[i][j][k][m] = -1;
  m = solve(0,C,D,0,-1);
  printf("%d\n",m);
  output(0,C,D,0,-1);

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1814-f47f8cbe
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。