spoj PARTIT

三维DP 第K字典序从左向右找根据dp数组的值算出每一位该打印什么
代码：
 1 #include <cstdio>
 2 #include <cstring>
 3 using namespace std;
 4 long long memo[9][221][221];
 5 long long solve(int n, int m, int last)//n划分成m个数最小值为last；
 6 {
 7     if(n==0)
 8     {
 9         if(m>=last) return 1;
10         return 0;
11     }
12     long long &ret = memo[n][m][last];
13     if(ret == -1)
14     {
15         ret = 0;
16         for(int i = last; (n+1) * i <= m; ++i)
17             ret += solve(n-1,m-i,i);
18     }
19     return ret;
20 }
21 
22 int main()
23 {
24     int T,M,N,K;
25     scanf("%d",&T);
26     while(T--)
27     {
28         scanf("%d %d %d",&M,&N,&K);
29         memset(memo,-1,sizeof(memo));
30         int last = 1;
31         for(int i = N-1; i>0; --i)
32         {
33             int tmp = 0,j = last;
34             while(true)
35             {
36                 if(tmp + solve(i-1,M-j,j) >= K)//如果它的字典序超过了目标；
37                 {
38                     printf("%d ",j);
39                     K -= tmp;
40                     last = j;
41                     M -= j;
42                     break;
43                 }
44                 tmp += solve(i-1,M-j,j);
45                 ++j;
46             }
47         }
48         printf("%d
",M);
49     }
50     return 0;
51 }
View Code