《算法周练7》部分题解

C：
思路：dp.
定义dp[i][j]为前i天工作了j天的最小代价.
思考如何转移：
当第i天为0时,直接可以从i-1继承.
那么为什么要继承？为了后续的计算.
当第i天为1时.先继承i-1,然后再加入第i天去更新.
如果更新？枚举到i的连续天数。
列如1 1 0 0 0 1 1 1.我们当前位置i为最后一个1,那么枚举连续的前面的天i-1,i-2.
当遇到了0,那就退出.因为这就不连续了,这时候的之前的连续的影响已经在之前被计算,所以就不用再去考虑.
然后我们既然保证了连续天应该是j-i。
那么显然j-1要保持休息,那么就从j-2开始转移.
很显然,当j=1的时候j-2已经会越界,这个时候显然j~i全部都连续,那么直接更新dp[i][i-j+1]即可.
Code:

定义dp[i][j]表示前i天做了j天工作的最小花费.
对于第i天为0的情况,直接继承第i-1天.
对于第i天为1的情况,枚举j表示从哪天开始连续工作i-j+1天.
如当前j到i为t天,那么从j-2转移来,因为从j开始工作,必须确保j-1休息.
int dp[405][405];
char s[405];
int main()
{
    int n,k;sdd(n,k);
    scanf("%s",s+1);
    for(int i=0;i<=n;++i)
        for(int j=0;j<=n;++j) dp[i][j] = INF;
    dp[0][0] = 0;
    for(int i=1;i<=n;++i)
    {
        for(int j=0;j<=i;++j)//不论是不是0都先继承,然后再去看是否要更新.
        {
            dp[i][j] = dp[i-1][j];
        }
        if(s[i] == '1')
        {
            for(int j=i;j>=1;--j)
            {
                if(s[j] == '0') break;//当已经无法连续时,就不需要再去更新.
                int t = i-j+1,sum = t*(t+1)/2;
                if(j == 1) dp[i][t] = min(dp[i][t],sum);
                else
                {
                    for(int m=i;m>=0;--m)//类似背包更新
                    {
                        if(m < t) break;
                        dp[i][m] = min(dp[i][m],dp[j-2][m-t]+sum);
                    }
                }    
            }
        }
    }
    int ans = -1;
    for(int i=0;i<=n;++i) if(dp[n][i] <= k && i > ans) ans = i;
    pr(ans);
    //system("pause");
    return 0;

}