CF1176F Destroy it!题解

题目大意：给定n个块，每个块内给你m个操作，其花费为w，攻击为v。每个块内不得选w总和超过3的操作（可以不选），总计选到第x个（x为10的倍数）时v可以翻倍，求v总和最大值
题解：一道简单到连我都能做出来的 DP
其实就是01背包的变式，多了一个v翻倍操作
设F[i][j]为做到第i个块，选了j个操作
因为空间不够，j%=10,这样不影响计算。
其实只有这么几个转移：{1，1，1}，{1，1}，{1}，{1，2}，{2}，{3}，（集合内代表w），直接做就好了
注意：可以不选，这些转移不一定可行，需要判断

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long 
using namespace std;
ll f[200005][15];
ll i,j,k,m,n,o,p,l,s,t,times,max1,max2,max3,max4,max5;
void read(ll &x)
{
    char ch=getchar();x=0;while (ch<'0'||ch>'9') ch=getchar();while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-48,ch=getchar();
} 
int main()
{
    
// freopen("destroy.in","r",stdin);
// freopen("destroy.out","w",stdout);read(n);memset(f,-60,sizeof(f));f[0][0]=0;for (i=1;i<=n;i++){
    read(m);max1=max2=max3=max4=max5=0;for (j=1;j<=m;j++) {
    read(o);read(p);if (o==1) {
    if (p>=max1) max3=max2,max2=max1,max1=p;else if (p>=max2) max3=max2,max2=p;else max3=max(max3,p);} else if (o==2) max4=max(max4,p);else max5=max(max5,p);}for (j=0;j<=9;j++) f[i][j]=f[i-1][j];for (j=1;j<=3;j++){
    for (k=0;k<=9;k++){
    if (j==1){
    if (f[i-1][k]>=0){
    if (max1) f[i][(k+1)%10]=max(f[i][(k+1)%10],f[i-1][k]+max1*(1+(k==9)));}} else if (j==2){
    if (f[i-1][k]>=0){
    if (max1&&max2) f[i][(k+2)%10]=max(f[i][(k+2)%10],f[i-1][k]+max1*(1+(k>=8))+max2);if (max4) f[i][(k+1)%10]=max(f[i][(k+1)%10],f[i-1][k]+max4*(1+(k>=9)));}} else if (j==3){
    if (f[i-1][k]>=0){
    if (max1&&max2&&max3) f[i][(k+3)%10]=max(f[i][(k+3)%10],f[i-1][k]+max1*(1+(k>=7))+max2+max3);if (max1&&max4) f[i][(k+2)%10]=max(f[i][(k+2)%10],f[i-1][k]+max(max1,max4)*(1+(k>=8))+min(max1,max4));if (max5) f[i][(k+1)%10]=max(f[i][(k+1)%10],f[i-1][k]+max5*(1+(k>=9)));} }}}}s=0;for (i=0;i<=9;i++) s=max(s,f[n][i]);printf("%lld\n",s);return 0;
}