2016年9月12日 星期一

ACM ICPC Singapore Regional 2015 Association for the Country of Mububa

/*
    題目連結

    感覺就很簡單的一題DP
    可是隊友一開始寫了個爛 greedy
    (就一直拿拿到 比前一個人拿得多就停止)

    這 greedy 是錯的
    因為考慮到你現在在發東西給第i個人
    你可能會希望讓第i-1個人多拿一點 讓第i個人少拿一點
    這樣你發給 第i+1以後的人 可能可以發得比較少

    Ex:
    5
    7 1 8 8 8 
    Ans:
    4

    所以呢 正確的做法是DP
    DP[i][j] 紀錄 最後一個人拿 第i~j箱的話
    最多可以讓多少人拿

    那轉移 就是 DP[i][j] = max(DP[k][i-1] for all k satisfy sum k to i-1 <= sum i to j)+1; 
    雖然說 這邊有個對於所有的 k 但是你這樣枚舉 k 是顯然會超時的
    注意到 滿足的 k 會是個區間 所以你可以事先算出個 min[i][j] 之類的東西
    再加上 二分搜就能過了

    因為這題是我想丟給隊友寫
    所以就附上周逸風格怪異 的 code
*/
#include <bits/stdc++.h>
using namespace std;
long long int dp[3005][3005];
long long int ar[3005];
long long int pf[3005];
long long int mx[3005][3005];
long long int sum(int l,int r){
    return pf[r+1]-pf[l];
    }
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%lld",&ar[i]),pf[i+1]=pf[i]+ar[i];
    long long int ans=0;
    for(int j=0;j<n;j++){
        for(int i=0;i<=j;i++){
            if(i==0)dp[i][j]=1;
            else{
                int l=0,r=i-1;
                while(l<=r){
                    int mid=(l+r)/2;
                    if(sum(i,j)>=sum(mid,i-1))
                        r=mid-1;
                    else
                        l=mid+1;
                    }
                //printf("%d %d\n",l,i-1);
                if(l!=i&&mx[l][i-1])
                    dp[i][j]=mx[l][i-1]+1;
                }
            //printf("$%d %d %d\n",i,j,dp[i][j]);
            ans=max(ans,dp[i][j]);
            }
        for(int i=j;i>=0;i--){
            mx[i][j]=dp[i][j];
            if(i!=j)
                mx[i][j]=max(mx[i][j],mx[i+1][j]);
            //printf("~%d %d %d\n",i,j,mx[i][j]);
            }
        }
    printf("%lld\n",ans);
    }

沒有留言:

張貼留言