題干：
?

小a有一個長度為nn的序列，但是他忘了這個序列的樣子，他只記得序列中的數大小在[1,V][1,V]內
你可以任意選擇一些位置，并給它們賦值來組成一段子序列，需要滿足序列中的數嚴格遞增
一段子序列的“萌值”定義為序列中除最大數外所有數的乘積，若只有11個數則為11
他想請你求出所有合法子序列的“萌值”的和
不同子序列的定義為：存在某個值不同 或 在原序列中的位置不同
輸出答案對109+7109+7取模

輸入描述:

兩個數n,Vn,V

輸出描述:

一個整數表示答案

示例1

輸入

復制

2 2

輸出

復制

5

說明

若X表示不選該位置，那么合法的方案有 1 X = 1 X 1 = 1 1 2 = 1 X 2 = 1 2 X = 1

示例2

輸入

復制

3 4

輸出

復制

55

說明

樣例2解釋:https://paste.ubuntu.com/p/xQwvD7Q3mX/

備注:

保證2?n,V?5000

解題報告：

dp[i][j]表示 : 截止到第i個位置，最大數是j的答案的值。狀態轉移的時候分為：第i個位置是否放數字，如果不放數字那就是dp[i-1][j]，如果放數字那就是統計一個和（因為第i-1個位置可以放1~j-1都要統計一遍，這里涉及很多重復計算，我們可以dp的時候直接維護下來，優化掉一層循環。） （賽后的題解好像解法比這個復雜一些、、維護了兩個數組）

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 5050; const ll mod = 1e9+7; ll dp[MAX][MAX];//dp[i][j] : 截止到第i個位置，最大數是j的 值 int main() {int n,v;cin>>n>>v;for(int i = 1; i<=v; i++) dp[1][i] = 1;for(int i = 2; i<=n; i++) {ll sum = 1;for(int j = 1; j<=v; j++) {dp[i][j] = (dp[i-1][j] + sum) % mod;sum = (sum + dp[i-1][j]*j) % mod;}}ll ans = 0;for(int i = 1; i<=v; i++) ans = (ans + dp[n][i]) % mod;printf("%lld\n",ans);return 0 ; }

?

AC代碼2：（注意取模問題）

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 5050; const ll mod = 1e9+7; ll dp[MAX][MAX];//dp[i][j] : 截止到第i個位置，最大數是j的 值 int main() {int n,v;cin>>n>>v;for(int i = 1; i<=v; i++) dp[1][i] = 1;for(int i = 2; i<=n; i++) {ll sum = i;dp[i][1] = i; for(int j = 2; j<=v; j++) {sum = (sum + dp[i-1][j]*j) % mod;dp[i][j] = (dp[i-1][j] + sum - dp[i-1][j]*j + 5000*mod) % mod;}}ll ans = 0;for(int i = 1; i<=v; i++) ans = (ans + dp[n][i]) % mod;printf("%lld\n",ans);return 0 ; }

?

總結

以上是生活随笔為你收集整理的【牛客 - 317F】小a的子序列（线性dp，tricks）的全部內容，希望文章能夠幫你解決所遇到的問題。

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