问题 J: Jack的宝物问题

题目描述

Jack是个吃鸡玩家，一个偶然的机会Jack来到了神秘的P城，Jack发现P城有 N 种宝物，每种宝物有 x[i] 个。但是当Jack想把他们全部拿走时，Jack发现由于背包限制，Jack现在只能带 3 件宝物回去，且每种宝物Jack最多只能带走 1 件。那么Jack一共有多少种带走 3 种不同宝物的方法？

输入

题目有多组测试数据

每组数据第一行输入一个m,代表m种类型(3<=m<=2000)

第二行有m个数，表述x[i](0<x[i]<=10000)

输出

对于每组数据，按题目要求输出一共有多少种方法(mod609929123)

样例输入

3
1 2 3      

样例输出

6      

思路：

感觉直接dp暴力会超时，但如果列举几个会发现，当选择了前两种宝物，会发现从第二件宝物的下一件宝物开始，到最后一件宝物，都会成为一次第三件宝物。

这就可以用前缀和来表示第三件宝物。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
 
using namespace std;
const int mo=609929123;
long long x[2005],dp[2005],su[2005];
int main()
{
    int n;
    while(cin>>n)
    {
        memset(dp,0,sizeof(dp));
        memset(su,0,sizeof(su));
        for(int i=1;i<=n;i++)
        {
            scanf("%I64d",&x[i]);
            su[i]=su[i-1]+x[i];
 
        }
        long long sum=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=i+1;j<=n;j++)
            {
 
                dp[i]=(dp[i]+((x[i]*x[j])%mo*(su[n]-su[j])%mo)%mo)%mo;
 
 
            }
            sum=(sum+dp[i])%mo;
        }
 
        cout<<sum<<endl;
    }
 
    return 0;
}