Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM502 DIV1 MEDIUM - TheProgrammingContestDivOne (この記事を編集する[管理者用])

Source

TopCoder SRM502 DIV1 MEDIUM (500pt)
Problem Statement
SRM502 DIV1 自分の参加記録

問題概要

codeforces formatみたいなコンテストを行う.
各問題を解くのに必要な時間が与えられたとき,最大スコアを求める問題.
正確に言うと,コンテスト時間T (100000以下) が与えらる.(ちょうどT後はサブミットできる)
また,各問題 (問題数は50以下) に対して 最高点と減少点,その問題を解くのに必要な時間が与えられる.
問題を解いて得られる点数は
 最高点 - 減少点 * コンテスト開始時からその問題を解き終わるまでに経過した時間
でマイナスになることもある.

解法

解く問題が固定されてるとしたら,
 減少点 / 解くのに必要な時間
が大きい問題から解いたほうが良い.
後は,どの問題を解くかは,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 ll long long

int n, t, mx[60], de[60], need[60];
ll dp[60][110000];

ll solve(int st,int tm){
  int i,j,k;
  ll res = 0, tmp;

  if(dp[st][tm] >= 0) return dp[st][tm];
  if(st==n) return dp[st][tm] = 0;

  res = solve(st+1,tm);
  if(tm + need[st] <= t){
    tmp = solve(st+1, tm+need[st]);
    tmp += mx[st] - de[st] * (ll)(tm+need[st]);
    if(res < tmp) res = tmp;
  }

  return dp[st][tm] = res;
}

class TheProgrammingContestDivOne {
public:
int find(int T, vector <int> maxPoints, vector <int> pointsPerMinute, vector <int> requiredTime) {
  int i,j,k;
  pair<double, int> s[100];

  n = maxPoints.size();
  t = T;

  rep(i,n) s[i].second = i, s[i].first = (double)requiredTime[i] / (double)pointsPerMinute[i];
  sort(s, s+n);

  rep(i,n){
    mx[i] = maxPoints[s[i].second];
    de[i] = pointsPerMinute[s[i].second];
    need[i] = requiredTime[s[i].second];
  }

  rep(i,n+1) rep(j,t+2) dp[i][j] = -1;

  return (int) solve(0,0);
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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