【刷题】【dp】【记忆化搜索】单词游戏

题目地址

https://www.luogu.com.cn/problem/P1278

设计巧妙的二维dp

开始我的想法是：记录每一个集合s（状态压缩表示），和最后的单词结尾

这样理应是没有后效性的，

结果样例都过不去，只好一直调试找错

原来是我实际的定义与理想的定义不同，我实际写的时候，二维数组的值表示的是：最后一个单词+其后面能接的最大长度

#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iostream>
using namespace std;

int n,ans;
const int N=(1<<16);
int f[20][N];
int head[20],tail[20],len[20];

int Get(char ch)
{
    if(ch=='A') return 1;
    else if(ch=='E' ) return 2;
    else if(ch=='I' ) return 3;
    else if(ch=='O' ) return 4;
    else return 5;
}

int dfs(int x,int state)
{
    if(f[x][state] ) return f[x][state];
    else f[x][state]=len[x];
    
    for(int i=0;i<n;i++)
        if(head[i]==tail[x] && (state&(1<<i))==0 )
            f[x][state]=max(f[x][state], dfs(i,state+(1<<i) )+len[x] );
    return f[x][state];
} 

int main()
{
    cin>>n;
    string s;
    for(int i=0;i<n;i++)
    {
        cin>>s;
        len[i]=s.length() ;
        head[i]=Get(s[0]),tail[i]=Get(s[len[i]-1]);
    }
    
    for(int I=0;I<n;I++)
        ans=max(ans,dfs(I,(1<<I)) );
    cout<<ans;
    
    return 0;
}       

View Code