題目鏈接：http://www.topcoder.com/stat?c=problem_statement&pm=10369&rd=13699一開(kāi)始想貪心＋遞歸做。。。始終fail systemtest。。
貪心無(wú)法證明，還是用dp了。
若用遞推，復(fù)雜度為O(10^6*10*50)=O(5*10^8)，應(yīng)該會(huì)超時(shí)。。可能在tc的牛機(jī)上不會(huì)超。。。
用memoization的dp就不會(huì)超了,因?yàn)榇蟛糠譅顟B(tài)是不會(huì)到達(dá)的。
#include <algorithm>
#include <sstream>
#include <string>
#include <iostream>
//44M內(nèi)存。。。空間不會(huì)超
int dp[1000001][11];
using namespace std;
class TheSwap
{
public:
int findMax(int n, int k)
{
// memset -1 從語(yǔ)義上說(shuō)是不對(duì)的，只是-1為全1，4個(gè)byte恰好拼成一個(gè)int時(shí)還是-1
memset(dp,-1,sizeof(dp));
//將n轉(zhuǎn)化成字符串。貌似gcc不支持itoa函數(shù),不是標(biāo)準(zhǔn)函數(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];
}