Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM462 DIV2 HARD - SteeplechaseTrack (この記事を編集する[管理者用])

Source

TopCoder SRM462 DIV2 HARD (1000pt)
Problem Statement

問題概要

ノード数50以下の有向グラフが与えられる.
スタート場所から各ノードまでの距離,各ノード間の距離,各ノードから終了場所までの距離も与えられる.
また,各ノードを通るごとに距離がさらにノードに設定された数字だけ足される.
高々ノードをN個以下しか通らない最大の距離を求める問題.
Nは100以下.

解法

問題の形式が少し面倒なだけで,普通のDP.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define INF 1000000000

class SteeplechaseTrack {
public:
int maxComplexity(vector <string> fences, vector <string> tracks, int N) {
  int i,j,n=fences.size();
  int res;
  int dp[55], next[55];
  int edge[55][55];

  rep(i,n+1) rep(j,n+1) edge[i][j]=-INF;
  rep(i,n){
    if(fences[i][1]!='0') edge[n][i]=(fences[i][1]-'0')+(fences[i][0]-'0');
    rep(j,n) if(tracks[j][i]!='0') edge[j][i]=(tracks[j][i]-'0')+(fences[i][0]-'0');
  }

  res=-1;
  rep(i,n) dp[i]=-INF; dp[n]=0;
  while(N--){
    rep(i,n+1) next[i]=-INF;
    rep(i,n+1) if(dp[i]>=0) rep(j,n+1) if(edge[i][j]>=0) if(next[j] < dp[i]+edge[i][j]) next[j]=dp[i]+edge[i][j];
    rep(i,n+1) dp[i]=next[i];

    rep(i,n) if(fences[i][2]!='0' && res < dp[i]+(fences[i][2]-'0')) res = dp[i]+(fences[i][2]-'0');
  }


  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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