読者です 読者をやめる 読者になる 読者になる

SRM612 Div1Easy EmoticonsDiv1

問題概要
はじめからある 1文字を「コピー」「ペースト」「1文字削除」の三操作を用いて、目的の個数にする最小操作回数を求めよ。

解法

dp[i] := i個の文字が描画されるための最小操作回数

j ( 1<=j ) 回以上連続して貼り付けを行うループと、その貼付けに対して連続して k ( 1

#include<bits/stdc++.h>
using namespace std;
#define INF (1<<29)
class EmoticonsDiv1 {
public:
  int const MAX = 1000;
  int printSmiles(int smiles) {
    
    int dp[1010];
    fill(dp, dp+1010, INF);
    dp[1] = 0;
    for(int i=1; ; i++) {
      if(i > MAX) break;
      for(int j=2; ; j++) {
        if(j*i > MAX) break;
        dp[j*i] = min(dp[j*i], dp[i] + j);
        for(int k=1; k<j; k++) {
          dp[j*i-k] = min(dp[j*i-k], dp[i] + j+k);
        }
      }
    }
    
    return dp[smiles];
  }
};