dp

D - Flipping and Bonus（线性dp)

D题戳这里

题意 有一个计数器，计数器cnt可以cnt++orcnt=0。cnt++时能够得到xi的奖励，以及得到对应cnt的额外奖励。问怎样进行操作能够得到最多的奖励(非常典型的二选一dp操作）

设dp[i][j]为第i步选择的是cnt++操作得到的最大值，dp[i][0]为第i步选择的是cnt=0的最大值。

状态转移方程:

dp[i][j]=dp[i-1][j-1]+x[i]+mp[j]
dp[i][0]=max(dp[i][0],dp[i-1][k]

最后取最大值

void solve()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>x[i];
	for(int i=1;i<=m;i++){
		ll c,y;
		cin>>c>>y;
		mp[c]=y;
	}
	for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++)
            dp[i][j]=dp[i-1][j-1]+x[i]+mp[j];
        dp[i][0]=0;
        for(int k=1;k<i;k++)//要求dp[0]是因为j=1时前一步是0
            dp[i][0]=max(dp[i][0],dp[i-1][k]);
    }
	ll maxn=0;
	for(int i=1;i<=n;i++)//最后全部取最大值是因为后面可能全部是置0
		maxn=max(maxn,dp[n][i]);
	cout<<maxn<<endl;
	return;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

E - Many Operations（数位dp）

E题戳这里

题意： 有三种操作：
1.T=1时，x=x&a;
2.T=2时，x=x|a;
3.T=3时，x=x^a;
有n次操作，每次给定T,a，将x进行i次T操作，每次的a等于对应前面次数的a，输出每一次的答案

设dp[i][j][k]为第i次操作第j位是0或者1(用k记录)的值，记录数位的值最后相加就能够得到结果

状态转移方程：

T=1,f[i][j][k]=f[i-1][j][k]&(a[i]>>j&1)
T=2,f[i][j][k]=f[i-1][j][k]|(a[i]>>j&1)
T=3,f[i][j][k]=f[i-1][j][k]^(a[i]>>j&1)

void solve()
{
	int n,x;
	cin>>n>>x;
	for(int i=1;i<=n;i++)
		cin>>t[i]>>a[i];
	for(int i=0;i<30;i++)
		f[0][i][0]=0,f[0][i][1]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<30;j++){
			for(int k=0;k<2;k++){
				if(t[i]==1)f[i][j][k]=f[i-1][j][k]&(a[i]>>j&1);
				else if(t[i]==2)f[i][j][k]=f[i-1][j][k]|(a[i]>>j&1);
				else if(t[i]==3)f[i][j][k]=f[i-1][j][k]^(a[i]>>j&1);
			}
		}
	}
	for(int i=1;i<=n;i++){
		int res=0;
		for(int j=0;j<30;j++)
			res+=f[i][j][x>>j&1]<<j;
		cout<<res<<endl;
		x=res;
	}
	return;
}
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

---

总结

写dp应该定义好状态，想好转移方程并记录转移数值，不同情况分开写。注意初始化问题。