xjoj 146快速ブラシスクリーン--簡単なdpは意外にもdpが時計を打つとは思わなかった

主にタイトルの文字列を见て最大1 w个、表暴力を振るったら1 w*5 kの复雑さだったはずなのに、続けられなかった、终わった后に発见したのは确かにこの考えだった...いいですね.これからはそうしないでほしいです.

/*
http://202.117.21.117/xjoj/problem_html/146.html     
dp[i] :    i        
dp[i] = min(dp[i-1] + 1 , dp[j] + time*2 + 5 );
j      j      ，time        
*/
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;

int dp[10001];

int main(){
    dp[0] = 0;
    for(int i = 1 ; i <= 10000  ;i++){
        dp[i] = dp[i-1] + 1;
        for(int j = 1 ; j < i ; j++){
            int times = ((i-j) % j == 0) ? ((i-j) / j) : ((i-j) / j + 1) ;
            int last  = dp[j] + times*2 + 5;
            if(dp[i] > last)
               dp[i] = last;
        }
    }
    int T;cin >> T;
    while(T--){
        int n;
        scanf("%d",&n);
        printf("%d
",dp[n]);
    }
    return 0;
}