HDU3905 Sleeping



Sleeping

題目鏈接：Click Here~

題目分析：

又是一道DP題，每次都是一眼看穿，每次都是不會正確推出狀態轉移方程式。悲劇。。~-~

說有一個搞ACM的人，天天逃課搞ACM。但是快到期末了，他為了學分只能去上課了。由於他是熬夜刷題，所以他總是在課堂上睡覺（orz）。為了學分，他決定不能繼續睡下去了。於是他制定了一個計劃，就是在一堂課的n分鐘中連續的聽老師講課不小於L分鐘，但是每堂課睡覺時間不能少於m分鐘（畢竟不是神啊，還是需睡覺地-_-）。而且每堂課每分鐘都有一個學分值，現在要你求出在滿足了上面的要求下如何得到最大的學分。學分是主要啊！這個大家都懂的。

算法分析：

我個人感覺跟那個啥，跟HDU的Sum plus plus有點像。就是要運用到相同的思想，但是差別還是有點的，就是Sum plus plus更難一點。說說這題如何推狀態轉移方程式吧。

我們用dp[i][j]表示前i分鐘睡覺用了j分鐘的最大學分值。

=====>>則可以推出一個狀態：dp[i][j] = max(dp[i-1][j-1],dp[i-1][j]+a[i]);

這個的意思是在第i分鐘是睡還是不睡，去其中的最大值。而我們知道其中不睡還有分兩種情況，這就是這道題的精髓所在，也就是為什麼我說跟Sum plus plus有點像的原因。

第一種：把第i分鐘不睡的值歸入到前面的不睡的時間中。（在i分鐘裡連續聽課的時間不一定大於L）

第二種：以第i分鐘結尾，把前i-L作為開始聽課的起點。且我們必須保證前提i-L>=j(因為至少要保證有前i分鐘又j分鐘的睡覺時間啊！)。

為什麼要這麼麻煩的分兩種情況呢?你如果認真思考過，應該就會知道了。如果，直接求得話時間復雜度是O(N^3)。

所以，最後我們會得到最後的狀態是：

d[i][j] = max{d[i-1][j]+a[i](接著前面不睡的時間),dp[i-L][j]+sum[i]-sum[i-L](以i-L作為不睡的起點)}。

最後吐槽一下HDU的判題系統，我看到有的人寫的程序都超數組下界了還可以AC。

#include 
#include 
#include 
#include 
using namespace std;

const int maxn = 1e3 + 5;
int dp[maxn][maxn],d[maxn][maxn];
int sum[maxn],a[maxn];
int n,L,m;
int Solve()
{
    memset(dp,0,sizeof(dp));
    memset(d,0,sizeof(d));
    for(int i = 1;i <= n;++i){
        for(int j = 0;j<=i&&j <= m;++j){
            if(i-ll >= j)
              d[i][j] = max(d[i-1][j]+a[i],dp[i-ll][j]+sum[i]-sum[i-ll]);    //不睡的最大收益
            if(j>=1)             //注意這裡！！
              dp[i][j] = max(d[i][j],dp[i-1][j-1]);
            else
              dp[i][j] = d[i][j];
//            printf("j-1---> %d\n",j-1);
        }
    }
    return dp[n][m];
}
int main()
{
    while(~scanf("%d%d%d",&n,&m,&L))
    {
        sum[0] = 0;
        for(int i = 1;i <= n;++i){
            scanf("%d",&a[i]);
            sum[i] = sum[i-1]+a[i];
        }
        printf("%d\n",Solve());
    }
    return 0;
}