題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=5086

題目大意：給出長度為n的數組，然后要求累計里面的每個子串的和。

解題思路：這道題直接枚舉肯定不行，所以要找遞推關系。

假設：{1,2,3,4}為某一個序列，假設我們已經找到了{1,2,3}，接下來把{4}加入進去；

由于{1,2,3}已經有{1},{2},{3},{1,2},{2,3},{1,2,3},那么我們需要觀察，把{4}放進去會有哪些影響，

首先會多出{3,4},{2,3,4},{1,2,3,4},{4}，這是突破口，我們只要找到[k,3]的所有和，再把{4}給補上即可。

這樣我們就有遞推式：dp[i] = dp[i-1] + tmp[i-1] + i * a[i]，其中dp[i]表示前i個序列的子串和，tmp[i]表示sum{[k,i]}，k-i的總和。

由于要取模，所以必須把所有的數都要變成__int64，這里WA若干次。

#include<iostream> #include<cstdio> #include<cstring> using namespace std;const int maxn = 447005; const int mod = 1e9+7; int n; __int64 a[maxn],dp[maxn],tmp[maxn];int main() {int t;scanf("%d",&t);while(t--){scanf("%d",&n);for(int i = 1; i <= n; i++)scanf("%I64d",&a[i]);dp[1] = tmp[1] = a[1];for(int i = 2; i <= n; i++)tmp[i] = (tmp[i-1] + i * a[i] % mod) % mod;for(int i = 2; i <= n; i++)dp[i] = (dp[i-1] + tmp[i-1] + i * a[i] % mod) % mod;printf("%I64d\n",dp[n]);}return 0; }

總結

以上是生活随笔為你收集整理的hdu 5086(dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

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