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