1456: 逃票的chanming(3)
时间限制: 2 Sec 内存限制: 128 MB提交: 326 解决: 48[][][]题目描述
这是一个神奇的国度。
这个国度一共有N个城市组成，让我们将他们编号为1~N，
这一天，chanming带着他的第一个月的工资K元来到了城市1。他想到城市N去寻找宝藏。经历了艰难险阻，上刀锅下油山，他终于来到了N市。在这里，他发现了n种宝藏。每一种宝藏有a[i]个。
Chanming是个有情有义的人，他怎么会忘记自己的小伙伴呢~他决定带着3件宝藏回去向他的三个小伙伴炫耀！他是这样考虑的：
他要带3件宝藏回去。
同一种类的宝藏他至多只带1件。
现在Chanming想知道知道他有多少种不同的方案。
输入
题目包含多组数据，你需要处理到文件结束（EOF）
每组数据第一行一个正整数n，表示n种类型(3 <= n <= 3000)
第二行有n个数，表述a[i] (a[i] <= 10000)
输出
对于每组数据，输出一个数，表示总共有多少种不同的选择(mod 400823823)
样例输入
31 2 3
样例输出
6
提示
来源
注意组合的状态，新增加一种后，前面的组合形式有三种。dp的作用就是不断更新这三种状态，第三种状态就是当前的最大种数。
#include#include #include #include using namespace std;#define maxn 10010int main(){ int a[maxn],n; long long dp[maxn][4]; while(cin >> n) { for(int i=1;i<=n;i++) cin >> a[i]; dp[3][3] = (a[1]*a[2]*a[3])%400823823; dp[3][2] = (a[1]*a[2] + a[1]*a[3] + a[2]*a[3])%400823823; dp[3][1] = (a[1]+a[2]+a[3])%400823823; for(int i=4;i<=n;i++) { dp[i][3] = (dp[i-1][3]+dp[i-1][2]*a[i])%400823823; dp[i][2] = (dp[i-1][2]+dp[i-1][1]*a[i])%400823823; dp[i][1] = (dp[i-1][1] + a[i])%400823823; } cout << dp[n][3] << endl; } return 0; }