大家好，欢迎来到IT知识分享网。
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)
样例输入
3
1 2 3
样例输出
6
提示
来源
GDUT校赛
注意组合的状态，新增加一种后，前面的组合形式有三种。dp的作用就是不断更新这三种状态，第三种状态就是当前的最大种数。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define maxn 10010 int 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; }
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/29629.html
