題目鏈接：點擊查看

題目大意：給出n個數字組成的序列，現在規定“好數組”指的是一個連續序列a1,a2,...ak的a1=k-1，再規定“好序列”是可以分為若干個“好數組”的序列，現在問這n個數字中有多少個子序列是“好序列”

題目分析：這個題目的好數組+好序列=好序列，而且好數組只與第一項有關，所以我們可以從后向前遞推，dp[i]代表的是i~n之中好序列的個數，這樣我們設計出的轉移方程就是for(j:a[i]+i+1,n+1),dp[i]=dp[j]*c[j-i-1][a[i]]，后面的c數組表示的是組合數，c[a][b]代表的就是從a中選b個物品的方案數，我們直接用C就可以求出當前j-i-1這段區間中能組合出多少種以i為開頭的好數組，然后搭配上第j位置上的好序列的個數，就可以一直向前遞推了，時間復雜度是n*n

煩人的dp。。我的dp真的是一點都不會，哭了，能看懂別人設計的轉移方程，但自己就是設計不出來

對了，這里需要解釋一下為什么要將dp[n+1]設置為1，因為我們以上都是考慮的好數組+好序列構成的好序列，而忘記了好數組單獨也能成為一個好序列，所以我們將最后的位置放寬到n+1，這樣就能正確枚舉所有好數組單獨構成的好序列了

這個題目也是讓我學到了組合數還能用遞推的形式O(n)打表，公式：

C[i][j]=C[i-1][j-1]+C[i-1][j]

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e3+100;const int mod=998244353;int a[N];LL c[N][N],dp[N];void init()//預處理組合數 {for(int i=1;i<N;i++)for(int j=1;j<N;j++){if(j==1)c[i][j]=i;elsec[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;} }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);init();int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",a+i);dp[n+1]=1;//將位置放寬到n+1for(int i=n-1;i>=1;i--)//枚舉每個位置{if(a[i]<=0||a[i]+i>n)continue;for(int j=a[i]+i+1;j<=n+1;j++)//記錄每個位置的貢獻dp[i]=(dp[i]+dp[j]*c[j-i-1][a[i]]%mod)%mod;}LL ans=0;for(int i=0;i<n;i++)ans=(ans+dp[i])%mod;printf("%lld\n",ans);return 0; }

?

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的CodeForces - 1000D Yet Another Problem On a Subsequence(动态规划+组合数学)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。