巨佬们看一下有什么问题,打的是subtask1-3
蒟蒻实在是看不出来问题在哪qwq
//这个就是题解那个O(N3)的做法
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MaxN = 1005;
LL N, P, Q, K;
LL F[MaxN][MaxN], Val[MaxN][MaxN];
LL S[MaxN], Sum[MaxN], V[MaxN], T[MaxN];
int main()
{
cin >> N;
for (LL i = 1; i <= N - 1; ++i)
{
cin >> S[i];
Sum[i + 1] = Sum[i] + S[i];
//题解中的ns
}
for (LL i = 1; i <= N; ++i)
{
cin >> V[i];
}
cin >> P;
while (P--)
{
for (LL i = 1; i <= N; ++i)
{
cin >> T[i];
}
for (LL i = 1; i <= N; ++i)
{
for (LL j = i; j <= N; ++j)
{
Val[i][j] = Val[i][j - 1] + (Sum[j] - Sum[i]) - (T[j] - T[i]);
//就是题解中的val
}
}
memset(F, 127, sizeof(F));
F[0][0] = 0;
for (LL i = 1; i <= N; ++i)
{
for (LL k = 1; k <= i; ++k)
{
//循环求Fi,k
for (LL j = 0; j <= i - 1; ++j)
{
F[i][k] = min(F[i][k], F[j][k - 1] + Val[j + 1][i] * V[j + 1]);
}
}
}
cin >> Q;
while (Q--)
{
cin >> K;
if (K < N)
{
cout << F[N][K] << " ";
}
else
{
cout << "0 ";
}
}
cout << endl;
}
return 0;
}