题目链接：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就不会超了,因为大部分状态是不会到达的。
#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函数,不是标准函数
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];
}