Codeforces 167B 状态设置的优化

题意：

一名参赛者有一个能装下$k$份奖金的袋子。有$n$场比赛，每场比赛中的胜者会被奖励一个大小为$a_i$的袋子或者是一份奖金。当参赛者赢得至少$l$场比赛会被认为是发挥良好。参赛者每次赢的一场比赛后赢的得奖金不必立刻放入他的背包，它可以完成所有比赛后带着所有背包回来装奖金，每场比赛获胜的概率是$p[i]$，问最后发挥良好并且能够带走他赢下的所有奖金的概率是多少？

方法：

显然是一个$dp$：

一开始的思路，设$dp[i][j][k]$为前$i$场，赢了$j$场，并且此时总容量为$k$的概率是多少。注意到最多装下$n$份奖金，于是$k>=n+1$的部分选择累加在$dp[i][j][n+1]$上。最后的答案应该是所有${\sum }_{j=l}^n{\sum }_{k=赢下的奖金场数}^{n+1}dp[n][j][k]$

我们维护的状态并不能反映赢下的奖金场数这一个概念，于是考虑这样写状态：

设$dp[i][j][k][l]$为前$i$场，赢了$j$场奖金场，$k$场背包场，容量为$l$，最后答案为$dp[n][j][k][l](l\ge i)$之和，这样时间复杂度和空间复杂度都是$O(n^4)$的，空间可以滚动压缩成$O(n^3)$，可惜时间复杂度不能优化了。

正解思路是这样，设$dp[i][j][k]$为前$i$场，赢了$j$场，此时容量剩余$k$，这样每次我们赢了一场奖金场，我们就可以在$k$上体现出来，由于$k$可能为负数，那么我们需要加上一个偏移量$maxn=200$，这样时间复杂度也为$O(n^3)$的

at all，设置状态可以选择设两个相互联系的变量来代替三个具体的变量，但并非是无用设置，无用设置比如说将$i$与$n-i$设为两个状态，这显然是没必要的。

#include
#define ll long long
using namespace std;

int n,l,kk,a[205];
double p[205],dp[205][205][405];

int main()
{
    cin>>n>>l>>kk; //一开始的只能装下k
    kk=min(kk,n);
    for(int i=1;i<=n;i++)
    {
        int tmp; cin>>tmp;
        p[i]=tmp*0.01;
    }
    for(int i=1;i<=n;i++) cin>>a[i];
    //最后表现良好，并且赢的奖品每次都有机会
    //dp[i][j][k] -> 前i场赢了j场。剩余空间为k
    dp[0][0][kk+200]=1;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<=i;j++)
        {
            for(int k=0;k<=401;k++)
            {
                if(a[i+1]==-1)
                {
                    if(k>=1) dp[i+1][j+1][k-1]+=dp[i][j][k]*p[i+1];
                    dp[i+1][j][k]+=dp[i][j][k]*(1-p[i+1]);
                }
                else
                {
                    dp[i+1][j+1][min(401,k+a[i+1])]+=dp[i][j][k]*p[i+1];
                    dp[i+1][j][k]+=dp[i][j][k]*(1-p[i+1]);
                }
            }
        }
    }
    double ans=0;
    for(int i=l;i<=n;i++)
        for(int j=200;j<=401;j++) ans+=dp[n][i][j];
    printf("%.10lf",ans);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45