Java教程

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

本文主要是介绍【刷题】【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

 

这篇关于【刷题】【dp】【记忆化搜索】单词游戏的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!