xtu1378

额…..

题目描述

给你一个n块积木，每个积木块都是立方体，现在把它们排列一排，成m列，要求每列上至少有1个积木，且从左到右，每列的积木数量呈严格单调下降。比如8块积木，排成3列，那么合法的安排方案为521或者431。请问n块积木按规则排成m有多少种不同的方案？

输入

第一行是一个整数T(1≤T≤1000)，表示样例的个数。

以后每个样例占一行，为两个整数 n(1≤n≤100),m(1≤m≤10)。

输出

依次每行输出一个样例的结果，为一个整数。

样例输入

2
8 3
13 4

样例输出

2
3

样例解释

第二个样例的合法方案为7321,6421,5431。

法一、暴力

因为n,m都很小，直接暴力即可，不是纯暴力，得优化一下。dp的方法刚开始没想到，主要是因为dp蒟蒻。

#include<bits/stdc++.h>
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
typedef pair<ll,ll> P;
const ll maxn=2e5+11;
ll ans,n,m;
void dfs(ll step,ll sum,ll fa){
    if(step==m-1){
        if(n-sum>fa)  ans++;
        return ;
    }
    ll x=(n-sum)/(m-step)+(step-m+1)/2+1;
    //这个x是根据题目要求递减推出来的一个上限,很容易推。
    //因为我这里是倒着推，推递增序列，所以下限是fa+1，上限是x。
    for(ll i=fa+1;i<=x;i++){
        dfs(step+1,sum+i,i);
    }
}
void solve(){
    ans=0;
    dfs(0,0,0);
    cout<<ans<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll ca;cin>>ca;
    while(ca--){
        cin>>n>>m;
        solve();
    }   
    return 0;
}

法2,dp