題目鏈接：http://www.topcoder.com/stat?c=problem_statement&pm=10369&rd=13699一開始想貪心＋遞歸做。。。始終fail systemtest。。
貪心無法證明，還是用dp了。
若用遞推，復雜度為O(10^6*10*50)=O(5*10^8)，應該會超時。。可能在tc的牛機上不會超。。。
用memoization的dp就不會超了,因為大部分狀態(tài)是不會到達的。
#include <algorithm>
#include <sstream>
#include <string>
#include <iostream>
//44M內存。。。空間不會超
int dp[1000001][11];
using namespace std;
class TheSwap
{
public:
int findMax(int n, int k)
{
// memset -1 從語義上說是不對的，只是-1為全1，4個byte恰好拼成一個int時還是-1
memset(dp,-1,sizeof(dp));
//將n轉化成字符串。貌似gcc不支持itoa函數(shù),不是標準函數(shù)
stringstream ss;
ss<<n;
string s;
ss>>s;
return _findMax(s,k);
}
int _findMax(string &s,int k){
int n = atoi(s.c_str());
if(k==0)
return n;
if(dp[n][k]!=-1)
return dp[n][k];
for(int i=0;i<s.size();++i){
for(int j=i+1;j<s.size();++j){
if(s[j]=='0'&&i==0){
// invalid
continue;
}
swap(s[i],s[j]);
dp[n][k] = max(dp[n][k],_findMax(s,k-1));
swap(s[i],s[j]);
}
}
return dp[n][k];
}