部分分求调
查看原帖
部分分求调
679239
Lindone楼主2024/7/16 14:39

巨佬们看一下有什么问题,打的是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;
}

2024/7/16 14:39
加载中...