連結：https://tioj.ck.tp.edu.tw/problems/1704

題目大意

今天有 $N$ 個橘子，每個橘子都有相異的重量。今天要挑出一些橘子，由重量小到大吃掉這些橘子。已知第 $i$ 在第 $j$ 順位吃掉的話，那就有 $A_{i, j}$ 的飽足感。問至少要吃幾顆橘子才能有至少 $k$ 的飽足感

題解

可以考慮動態規劃。先將橘子由小到大排序，用 $p_{i}$ 表示排完序後的橘子，原來的編號是什麼，設 $d p [i] [j]$ 表示全部吃了 $j$ 個橘子，且最後一顆是 $p_{i}$ 的最大飽足度，那可以很輕鬆地發現

d p [i] [j] = A_{p_{i}, j} + max_{j = 1, 2, \dots i - 1} d p [i - 1] [j]

因為max的部分可以在 $O (1)$ 時間解決掉，故該方法可以在 $O(n^2) 的時間找出滿足條件答案。

AC Code

#include<bits/stdc++.h>
using namespace std;

vector<pair<int,int>> d;

int m[2001][2001];
int dp[2001];

int calc(int N, int K)
{
    for(int j=1;j<=N;++j)
    {
        int mx = dp[j-1];
        for(int i=j;i<=N;++i)
        {
            int tmp = dp[i];
            dp[i] = mx + m[ d[i-1].second ][j];
            mx = max(mx, tmp);
            if( dp[i] >=K ) return j;
        }
    }
    return -1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int N,K,W;
    cin>>N>>K;
    for(int i=1;i<=N;++i)
    {
        cin>>W;
        d.emplace_back(W,i);
    }
    for(int i=1;i<=N;++i)
        for(int j=1;j<=N;++j)
            cin>>m[i][j];
    sort(d.begin(), d.end());
    cout<<calc(N, K)<<'\n';
}