dp递推题2010年吉林省省赛 1456: 逃票的chanming(3)

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; 
}