問題描述

　　小明想知道，滿足以下條件的正整數序列的數量：
1. 第一項為 n；
2. 第二項不超過 n；
3. 從第三項開始，每一項小于前兩項的差的絕對值。
　　請計算，對于給定的 n，有多少種滿足條件的序列。

輸入格式

　　輸入一行包含一個整數 n。

輸出格式

　　輸出一個整數，表示答案。答案可能很大，請輸出答案除以10000的余數。

樣例輸入

4

樣例輸出

7

樣例說明

　　以下是滿足條件的序列：
4 1
4 1 1
4 1 2
4 2
4 2 1
4 3
4 4

評測用例規模與約定

　　對于 20% 的評測用例，1 <= n <= 5；
　　對于 50% 的評測用例，1 <= n <= 10；
　　對于 80% 的評測用例，1 <= n <= 100；
　　對于所有評測用例，1 <= n <= 1000。

題目分析：模擬賽的時候看到n很小，并且自己也只會n^3的記憶化搜索，就直接暴力打了個表交上去了，因為題目強調了當前項和上一項之間的關系，所以 dp[ i ][ j ] 代表的就是前一項為 i ，當前項為 j 時的方案數，這樣在dfs里再套一層for就很簡單的寫出來了，n^3的方法就不多說了

重點是如何優化為 n^2 的算法，因為 dp[ i ][ j ] 的兩維是無法優化的了，可以著手考慮的是每次dfs里的那一層for循環能否優化掉，這里就可以借助前綴和的思想了，將 dp[ i ][ j ] 所表示的意義轉換為：前一項為 i ，當前項為 [ 1 , j ] 時的方案數，這樣最后的答案從先前的變為了 dp[ n ][ n ] ，轉移方程也比較巧妙（我自己反正推不出來）：

dp[ i?][ j ] = dp[ i ][ j - 1 ] + dp[ j ][ abs( i - j ) - 1 ] + 1

如何理解呢，因為 dp[ i ][ j ] 的意義轉換為了前綴和的思想，所以 dp[ i ][ j ] 在前一項固定的基礎上，應該是從當前項為 j - 1 時轉移而來，加上 前一項為 i ，當前項為 j 時的方案數就是 dp[ i ][ j ] 了，最后加上一是因為本身對答案也有貢獻，而前一項為 i ，當前項為 j 的答案，就可以利用題目給出的絕對值之差這個條件約束了，妙啊

動態規劃的題目一般都是只可意會不可言談。。

代碼：
?

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> //#include<set> #include<sstream> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e3+100;const int mod=10000;int dp[N][N];int dfs(int pre,int cur) {if(cur<=0)return 0;if(dp[pre][cur]!=-1)return dp[pre][cur];return dp[pre][cur]=(1+dfs(pre,cur-1)+dfs(cur,abs(pre-cur)-1))%mod; }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);memset(dp,-1,sizeof(dp));int n;scanf("%d",&n);printf("%d\n",dfs(n,n));return 0; }

?

總結

以上是生活随笔為你收集整理的蓝桥杯 - 序列计数(记忆化搜索)的全部內容，希望文章能夠幫你解決所遇到的問題。

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