cf761 Round #394 Div.2-C【DP+思维】

Date：2022.01.01

题意：n行m列的字符，每行只能选一个，且选完n个后至少分别存在一个数字、小写字母、’*’ || ‘#’ || ‘&’。

思路①：n、m<=50，试试能不能爆搜。dfs参数里标记每个元素的数量和移动的总步骤，当每个元素的数量和种类都满足条件时记录答案并跳出，然而会t。【注意比较烦人的是有的元素可能倒着走更近，预处理一下就好】

代码如下：

#include 
using namespace std;
const int N = 55;
typedef long long LL;
LL t,n,m,k;
bool st[N];
char c[N][N];
LL minn=1e9;
void dfs(int u,int digit,int latin,int symbol,LL sum)
{
    if(digit+latin+symbol>n||(digit+latin+symbol)==n&&(digit==0||latin==0||symbol==0)) return;
    if(u==n+1)
    {
        if(digit>0&&latin>0&&symbol)
        {
            minn=min(sum,minn);
            return;
        }
        else return;
    }
        for(int j=1;j<=m;j++)
        {
            if(c[u][j]=='*'||c[u][j]=='#'||c[u][j]=='&')
            {
                dfs(u+1,digit,latin,symbol+1,sum+j-1);
            }
            else if(c[u][j]>='0'&&c[u][j]<='9')
            {
                dfs(u+1,digit+1,latin,symbol,sum+j-1);
            }
            else if(c[u][j]>='a'&&c[u][j]<='z')
            {
                dfs(u+1,digit,latin+1,symbol,sum+j-1);
            }
        }
        for(int j=m;j>=1;j--)
        {
            if(c[u][j]=='*'||c[u][j]=='#'||c[u][j]=='&')
            {
                dfs(u+1,digit,latin,symbol+1,sum+m-j+1);
            }
            else if(c[u][j]>='0'&&c[u][j]<='9')
            {
                dfs(u+1,digit+1,latin,symbol,sum+m-j+1);
            }
            else if(c[u][j]>='a'&&c[u][j]<='z')
            {
                dfs(u+1,digit,latin+1,symbol,sum+m-j+1);
            }
        }
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) cin>>c[i][j];
    dfs(1,0,0,0,0);
    cout< 
 
 
思路②：dp。
 让f[i][j][k]：前i行存在j个数字、k个字母，因此间接存在至多i-j-k个符号，接着写转移方程。【之所以没标注符号个数为第四维是怕re】
 然后就是半天转移不出来，后来一想这样dp存在问题，首先存在符号不足或超过i-j-k个的情况，这样根本无法转移；其次关于符号个数的初始状态无法确认，这样转移很难做。
 
 
 
 
思路③：看了题解，dp照常，用三个状态f[i][0]、f[i][1]、f[i][2]表示从第i行第1个开始最近的数字、小写字母、符号，该行中没有则为INF。求答案时，我们只需枚举三种不同的东西分别在哪一行，但不让他们彼此之间同行。因此只需满足其中三行分别包含三种，其他行的元素都在第一个不用移动，这样总移动距离一定是最小的，好妙%%%。
 代码如下：
 
 
#include 
using namespace std;
const int N = 110;
typedef long long LL;
LL t,n,m,k;
char c[N][N];
LL f[N][4];
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>c[i][j];
    for(int i=0;i='0'&&c[i][j]<='9'))
                f[i][0]=min(f[i][0],min(j-1,m-j+1));
            if((c[i][j]>='a'&&c[i][j]<='z'))
                f[i][1]=min(f[i][1],min(j-1,m-j+1));
            if((c[i][j]=='*'||c[i][j]=='#'||c[i][j]=='&')) 
                f[i][2]=min(f[i][2],min(j-1,m-j+1));
        }
    }
    LL minn=1e9;
    //枚举三个不同符号分别在哪行，其它行无需移动即可
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
        if(i!=j)
            for(int k=1;k<=n;k++)
            {
                if(i!=k&&j!=k)
                    minn=min(f[i][0]+f[j][1]+f[k][2],minn);
            }
        }
    }
    cout<