P1329 数列

Ash_Dr · 2023-02-12 00:03:49 · 题解

为啥这个题这么久都没人写dp题解，我来补一发。

题目分析

考虑将原式化简为

设dp[i][j]表示考虑前i个x的取值，凑出的和为j,考虑x_i的取值，有dp转移式如下

这样就能求出方案数了。

输出方案数可以选择 dfs 输出方案，但是要注意一下剪枝，这里我用的是可行性剪枝，即如果后面 x_i 都取 1 或者都取 -1 无法满足条件，就 return。

其他要注意的地方：用unsigned long long 和dp时整体偏移一下。

int n,s;
ull dp[N][M];
ll biggest;
int cnt=0,path[N];
void dfs(int idx,int sum) {
    if(sum+(path[idx-1]+1+path[idx-1]+n-idx+1)*(n-idx+1)/2<s) return ;
    if(sum+(path[idx-1]-1+path[idx-1]-(n-idx+1))*(n-idx+1)/2>s) return ;
    if(idx==n+1) {
        if(sum==s) {
            for(int i = 1; i <= n; i++) cout<<path[i]<<" \n"[i==n];
            ++cnt;
            if(cnt==100) exit(0);
        }
        return ;
    }
    path[idx]=path[idx-1]+1;
    dfs(idx+1,sum+path[idx-1]+1);
    path[idx]=path[idx-1]-1;
    dfs(idx+1,sum+path[idx-1]-1);
}
void solve() {
    cin>>n>>s;
    biggest=(n-1)*n/2;
    dp[1][biggest]=1;
    for(int i = 2; i <= n; i++) {
        for(int j = 0; j <= 2*biggest; j++) {
            if(j-(i-1)>=0) dp[i][j]+=dp[i-1][j-(i-1)];
            if(j+(i-1)<=2*biggest) dp[i][j]+=dp[i-1][j+(i-1)];
        }
    }
    cout<<dp[n][s+biggest]<<"\n";
    path[1]=0;
    dfs(2,0);
}