CF1716D

标签：ch const int ll CF1716D DP define

Chip Move - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

背包DP：

这道题与完全背包不一样的地方便是：至少要拿一个物品。

DP[i,j]为前i个物品，每个至少拿一个，体积为j时的方案数

转移方程：DP[i,j]=DP[i-1,j-w[i]]+DP[i,j-w[i]]（具体见蓝书P277）

然后用滚动数组优化空间复杂度

由于是滚动数组，答案要及时统计

即便这样也是会TLE的，注意到每个物品至少拿一个，所以利用这点可以break来优化时间复杂度

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back   
#define popb pop_back  
#define fi first
#define se second
#define popcount __builtin_popcount
const int N=2e5+10;
const ll MOD=998244353;
//const int inf=1e9;
//const ll INF=1e18;
int T,n,k;
ll dp[2][N],ans[N];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
int main()
{
//    freopen("","r",stdin);
//    freopen("","w",stdout);
//    ios::sync_with_stdio(0);
//    cin.tie(0);
    n=read(),k=read();
    int minlen=0;
    dp[0][0]=1;
    for(int i=1;i<=n+k-1;i++)
    {
        int w=k+i-1;
        minlen+=w;
        if(minlen>n) break;
        for(int j=w;j<=n;j++) dp[ i%2 ][j]=(dp[ (i-1)%2 ][j-w]+dp[ i%2 ][j-w])%MOD;
        for(int j=0;j<=n;j++) ans[j]=(ans[j]+dp[ i%2 ][j])%MOD,dp[ (i-1)%2 ][j]=0;
    }
    for(int i=1;i<=n;i++) printf("%lld ",ans[i]);
    return 0;
}

 

 

 

标签：ch,const,int,ll,CF1716D,DP,define
From： https://www.cnblogs.com/Willette/p/17342225.html