本文主要是介绍问题 J: Jack的宝物问题（dp+前缀和），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题 J: Jack的宝物问题
时间限制: 1 Sec 内存限制: 128 MB提交: 594 解决: 77
状态
题目描述
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及前缀和的应用，两个for循环，确定两个位置，另一个位置可以都用前缀和表示出了
代码：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#define mod 609929123
#define ll long long
#define maxn 20010
using namespace std;ll n,a[maxn],sum[maxn];
ll ans;
int main()
{while(cin>>n){sum[0]=0;for(ll i=1;i<=n;i++){cin>>a[i];sum[i]=sum[i-1]+a[i];}ans=0;for(ll i=1;i<=n;i++){for(ll j=i+1;j<=n;j++){ans+=(a[i]*a[j]*(sum[n]-sum[j])%mod)%mod;}}cout<<ans%mod<<endl;}return 0;
}
这篇关于问题 J: Jack的宝物问题（dp+前缀和）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
