学步园

题目：点击打开链接

动态规划+状态压缩

1.对于一个序列:1,2,3...i，只要知道i前面m-1个点的状况，就能推断出i可以选择1，或0。而前m-1个点每一种确定的状态又可能对应两种情况，第前m个是0或1.

这里i表示当前序列最后一个位置，j表示前m个点所有的情况。

如果前m-1个中1的个数等于q：dp[i][j/2]=max{dp[i-1][j]};          最后一个点只能取1

如果前m-1个中1的个数等于q：dp[i][j/2+(1<<m)]=max{dp[i-1][j]}+w[i]; 

dp[i][j/2]=max{dp[i-1][j]};    

这里写的比较朴素的代码：

#include<iostream>
#include<cstdio>
using namespace std;
int w[1111], dp[1111][1111];
int f(int x, int m)
{
    int ans = 0;
    for(int i=1; i<=m; i++)
    {
        if(x%2==1) ans++;
        x/=2;
    }
    return ans;
}
int DP(int n, int m, int q)
{
    for(int i=1; i<=n; i++)
    {
        for(int j=0; j<(2<<m); j++)
        {
            //如果前M-1个中选的个数小于Q
            if(f(j/2,m)<q)
            {
                dp[i][j/2+(2<<(m-1))] = max(dp[i][j/2+(2<<(m-1))], dp[i-1][j]+w[i]);
                dp[i][j/2] = max(dp[i][j/2], dp[i-1][j]);
            }
            else if(f(j/2,m)==q)
            {
                dp[i][j/2] = max(dp[i][j/2], dp[i-1][j]);
            }
        }
    }
    int ans = -1000000;
    for(int j=0; j<(2<<m); j++)
    {
        ans = max(ans, dp[n][j]);
    }
    return ans;
}
int main()
{
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1; i<=n; i++) cin>>w[i];
    cout<<DP(n,m-1,q)<<endl;
    return 0;
}

改进1：减少空间，dp[n][1<<m]可以缩减为d[2][1<<m]，因为每次只要比较当前状态和前一个状态，只要用flag=0, flag^=1来处理就行了。

改进2：由于直接排出奇数的情况，for循环可以写成for(int j=0; j<(1<<m); j+=2)。