Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

2010 Round 1A B問題 - Make it Smooth (この記事を編集する[管理者用])

Source

Google code jam 2010 Round 1A B問題
Problem Statement
2010 Round 1A 自分の参加記録
SPOJ 6700 [GCJ101AB] (2010/05/28 05:20追記)

問題概要

0以上255以下を要素に持つ長さNの整数列が与えられる.
それの隣り合う項の差をM以下にするために必要なコストを求める問題.
できる操作は以下の3種類.
 コストDで1要素を消す
 コストIで好きな場所に好きな要素を挿入する
 コスト1である要素の数字を1だけ増やすか減らす
small: Nは3以下
large: Nは100以下

解法

 dp[今見てる場所(この場所の前までは条件を満たしている)][一つ前の数字]
でDPしようとしたら,ループしたので,ベルマンフォードっぽく書いた.
2010/05/28 05:20追記 ループのない形のちゃんとした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 ab(int x){if(x<0) return -x; return x;}

int koushin;
int dp[120][300];
int in[120], D, I, M, n;

void solve(int st,int bef){
  int i,j,k,res=1000000000,add,tmp;

  rep(i,256){
    add = ab(bef-i) - M; if(add > 0) continue;
    k = dp[st][i] + I;
    if(res > k) res = k;
  }

  rep(i,256){
    add = ab(bef-i) - M; if(add > 0) continue;
    tmp = ab(i-in[st]);
    k = dp[st+1][i] + tmp;
    if(res > k) res = k;
  }

  k = dp[st+1][bef] + D;
  if(res > k) res = k;

  if(dp[st][bef] > res) koushin++;
  dp[st][bef]=res;
}

int main(){
  int i,j,k,l,m,res;
  int size, count=0;

  scanf("%d",&size);
  while(size--){
    fprintf(stderr,"%d\n",size);
    scanf("%d%d%d%d",&D,&I,&M,&n);
    rep(i,n) scanf("%d",in+i);

    rep(i,n) rep(j,256) dp[i][j]=1000000000; rep(j,256) dp[n][j]=0;

    res = 1000000000;
    for(i=n-1;i>=0;i--){
      for(;;){
        koushin=0;
        rep(j,256) solve(i,j);
        if(koushin==0) break;
      }
    }
    rep(i,256) if(res>dp[0][i]) res=dp[0][i];
    printf("Case #%d: %d\n",++count,res);
  }

  return 0;
}
Cによるスパゲッティなソースコード (2010/05/28 05:20追記)
#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)

#define INF 1000000000
int dp[110][300];

int ab(int x){ if(x<0) return -x; return x; }

int main(){
  int i,j,k,l,m,n;
  int D,I,M;
  int in[110];
  int cost[256];
  int size,count=0;
  int res;

  scanf("%d",&size);
  while(size--){
    scanf("%d%d%d%d",&D,&I,&M,&n);
    rep(i,n) scanf("%d",in+i);

    rep(i,n+1) rep(j,256) dp[i][j]=INF;
    rep(j,256) dp[0][j]=0;

    cost[0]=0;
    if(M==0){
      REP(i,1,256) cost[i]=INF;
    } else {
      REP(i,1,256){
        k=i;
        cost[i]=0;
        while(k > M) cost[i]+=I, k-=M;
      }
    }

    rep(i,n) rep(j,256){
      if(dp[i+1][j] > dp[i][j]+D) dp[i+1][j]=dp[i][j]+D;
      rep(k,256) if(dp[i+1][k] > dp[i][j]+cost[ab(j-k)]+ab(in[i]-k))
        dp[i+1][k] = dp[i][j]+cost[ab(j-k)]+ab(in[i]-k);
    }

    res = INF;
    rep(j,256) if(res > dp[n][j]) res = dp[n][j];
    printf("Case #%d: %d\n",++count,res);
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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