2015年3月14日 星期六

[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 ;
    }
}

沒有留言:

張貼留言