题解 P3828 【[SHOI2012]火柴游戏】

hylhyl · 2018-10-18 17:24:03 · 题解

其实操作可以看成只有添加和删除两种 用一个二元数组dp[i][j]表示前i位数用j次添加操作最少要使用dp[i][j]次删除操作

枚举j，对于每一组添加和删除的操作集合（j，dp[n][j]）可以三分进行多少次转移操作。每进行一次转移操作相当于添加和减少操作数都减一.（其实枚举也能过。。。） ps：第二个样例有误，答案应为9，

#include<stdio.h>
#include<cmath>
#include<algorithm>
#include<string.h>
using namespace std;
const int maxn=205;
const int inf=0x7f7f7f7f7f;
int dp[maxn][505],p[5],q[5],n,ad[10][10],de[10][10];
int num[10][8]={{0,1,1,1,0,1,1,1},{0,0,0,1,0,0,1,0},{0,1,0,1,1,1,0,1},{0,1,0,1,1,0,1,1},{0,0,1,1,1,0,1,0},{0,1,1,0,1,0,1,1},{0,1,1,0,1,1,1,1},{0,1,0,1,0,0,1,0},{0,1,1,1,1,1,1,1},{0,1,1,1,1,0,1,1}};
char a[maxn],b[maxn];
int as(int s,int f)
{
    int i,ans=0;
    for(i=1;i<=7;i++)
    if(num[s][i]==num[f][i])continue;
    else if(num[s][i]==0) ans++;
    return ans;
}
int ds(int s,int f)
{
    int i,ans=0;
    for(i=1;i<=7;i++)
    if(num[s][i]==num[f][i])continue;
    else if(num[s][i]==1) ans++;
    return ans;
}
int getans(int i,int j)
{
    int ans=inf,k,l=0,maxk=min(i,j);
    for(k=0;k<=maxk;k++)
    {
        ans=min(ans,p[1]*(1+i-k)*(i-k)/2+(i-k)*q[1]+
        p[2]*(1+j-k)*(j-k)/2+(j-k)*q[2]+
        p[3]*(1+k)*k/2+k*q[3]);
    }
    return ans;
}
int main()
{
    int i,j,k,m,ans=inf;
    scanf("%d",&n);
    scanf("%s %s",a,b); 
    scanf("%d%d%d%d%d%d",&p[1],&q[1],&p[2],&q[2],&p[3],&q[3]);
    for(i=0;i<10;i++)
    {
        for(j=0;j<10;j++)
        {
            ad[i][j]=as(i,j);
            de[i][j]=ds(i,j);
        }
    }
    for(i=0;i<n;i++)
    {
        a[i]-='0',b[i]-='0';
    }
    for(i=1;i<=n;i++)
        for(j=0;j<505;j++)
            dp[i][j]=inf;
    for(m=1;m<=n;m++)
        for(k=0;k<10;k++)
        {
            int add=ad[a[m-1]][k]+ad[b[m-1]][k];
            int del=de[a[m-1]][k]+de[b[m-1]][k];
            for(i=0;i<505;i++)
                if(i>=add)
                dp[m][i]=min(dp[m][i],dp[m-1][i-add]+del);
        }
    for(i=0;i<505;i++)
        if(dp[n][i]!=inf)
        ans=min(ans,getans(i,dp[n][i]));
    printf("%d",ans);
    return 0;
}