10581 - Partitioning for fun and profit

题意：给定m, n，表示分配给n个格子，分配m个数字进去，每一个格子最少1，而且序列要是递增的，问第k个字典序的序列是什么

思路：先利用dp打出表，dp[i][j][k]表示第i个数，尾巴为j，总和剩下k的情况，写一个记忆化求出，之后在这个数组基础上，从左往右枚举要放那个数字合适，合适的就放进去而且输出，注意最后一个数字要单独输出。

代码：

#include 
     
      #include 
      
       typedef long long LL;int t, M, n, vis[15][225][225];LL k, dp[15][225][225];LL DP(int now, int tail, int m) {    LL &ans = dp[now][tail][m];    if (vis[now][tail][m]) return ans;    vis[now][tail][m] = 1;    ans = 0;    if (now == n) return ans = 1;    if (now == n - 1) {	if (m >= tail)	    return ans = DP(now + 1, m, 0);	return ans = 0;    }    for (int i = tail; i <= m - (n - now - 1); i++)	ans += DP(now + 1, i, m - i);    return ans;}void solve(LL k) {    int v = 1;    for (int i = 1; i < n; i++) {	for (int j = v; j <= M - (n - i); j++) {	    if (k > dp[i][j][M - j]) k -= dp[i][j][M - j];	    else {		M -= j;		v = j;		printf("%d\n", j);		break;	    }	}    }    printf("%d\n", M);}int main() {    scanf("%d", &t);    while (t--) {	memset(vis, 0, sizeof(vis));	scanf("%d%d%lld", &M, &n, &k);	DP(0, 1, M);	solve(k);    }    return 0;}