[TIOJ 1623] 國王烏龜的接駁車

作法：

題目要問的是「用 k 台車最多可以載幾隻」，反過來我們考慮「要載 k 隻最少要用幾台車」，設 dp[ i ][ j ] 代表在前 i 隻烏龜裡面，載 j 隻的最少車數，那麼在計算dp[ i ][ j ] 時有兩種可能：

1. 不選第 i 隻，這樣就是 dp[ i-1 ][ j ]。
2. 選第 i 隻，那麼要轉移到 dp[ i-1 ][ j-1 ] 還是 dp[ i-1 ][ j-1 ]+1 ? 這會取決於當前 i-1 隻烏龜裡面載了 j-1 隻時，最後一台車剩下的最大容量( 按照他的規則，只和最後一台車有關 )，所以我們需要多一個 w[ i ][ j ] 代表在前 i 隻裡要載 j 隻，並且滿足車數最小時，最後一台車的最大剩餘容量。這樣就可以成功DP了。


code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=2000+10 ;
 
int dp[maxn],w[maxn] ;
int a[maxn] ;
 
main()
{
    int n,k,m ; scanf("%d%d%d",&n,&k,&m) ;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]) ;
 
    fill(dp,dp+maxn,maxn+1) ; dp[0]=0 ;
    for(int i=1;i<=n;i++) for(int j=i;j>=1;j--)
    {
        if(a[i]>m) continue ;
        if(w[j-1]>=a[i])
        {
            if(dp[j-1]<dp[j]) dp[j]=dp[j-1] , w[j]=w[j-1]-a[i] ;
            else if(dp[j-1]==dp[j]) w[j]=max(w[j],w[j-1]-a[i]) ;
        }
        else
        {
            if(dp[j-1]+1<dp[j]) dp[j]=dp[j-1]+1 , w[j]=m-a[i] ;
            else if(dp[j-1]+1==dp[j]) w[j]=max(w[j],m-a[i]) ;
        }
    }
    for(int i=1;i<=n;i++) if(dp[i]>k)
    {
        printf("%d\n",i-1) ;
        return 0 ;
    }
}