浙江理工大学2024年程序设计 A 春天到了

 输出：对于每组测试数据，输出 q行，第 i(1≤i≤q)i行有一个整数，表示 dp[m][k]的值。

分析：

     首先我们需要开两个数组，a[]存放序列a,b[]由数组a[]计算，用ans存放答案。对于每个查询，读取 l,r,k,根据序列 a 和查询参数进行动态规划计算，得到 dp[m][k] 的值。

代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t, n, q, l, r, k;
int a[100010] = { 0 };
int b[100010] = { 0 };
int c[100010] = { 0 };
signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> t;
	while (t--)
	{
		cin >> n;
		for (int i = 1; i <= n; i++)
		{
			cin >> a[i];
		}
		for (int i = 1; i <= n; i++)
		{
			b[i] = b[i - 1] + a[i];
		}
		cin >> q;
		for (int i = 1; i <= q; i++)
		{
			cin >> r >> l >> k;
			int ans = 0;
			int m = l - r + 1;
			ans += b[l] - b[r - 1];
			for (int i = 0; i < k; i++)
			{
				ans += (m - i) * (m - i);
			}
			cout << ans << "\n";
		}
	}
}