当前位置：网站首页>Invoker 2019CCPC Qinhuangdao Station I Question Simple DP

Invoker 2019CCPC Qinhuangdao Station I Question Simple DP

2022-08-09 07:04:00 【swust_fang】

Problem link

Each skill has 6 combinations, and the previous skill also has 6 combinations, so from this state, the 6 types are transferred from the 6 types of the previous type, and the minimum value can be taken.

If you don't read the question, it may be regarded as two states (hh

ss represents the current state, s[k] represents the previous state, and the check function represents the state transition required

dp[i][j]=min(dp[i-1][k]+check(s[k],ss),dp[i][j])

Code:

//#pragma comment (linker, "/STACK:102400000,102400000")//#include#include#include#include#include#include#include#include#include#include#include#include#include#include#define myself i,l,r#define lson i<<1#define rson i<<1|1#define Lson i<<1,l,mid#define Rson i<<1|1,mid+1,r#define half (l+r)/2#define lowbit(x) x&(-x)#define min4(a, b, c, d) min(min(a,b),min(c,d))#define min3(x, y, z) min(min(x,y),z)#define max3(x, y, z) max(max(x,y),z)#define max4(a, b, c, d) max(max(a,b),max(c,d))typedef unsigned long long ull;typedef long long ll;#define pii make_pair#define pr pairconst int inff = 0x3f3f3f3f;const long long inFF = 9223372036854775807;const int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};const int mdir[8][2] = {0, 1, 0, -1, 1, 0, -1, 0, 1, 1, -1, 1, 1, -1, -1, -1};const double eps = 1e-10;const double PI = acos(-1.0);const double E = 2.718281828459;using namespace std;const int mod=998244353;const int maxn=3e5+5;const int maxm=1e6+5;map m;char str[maxn];ll dp[maxn][6];int check(string s,string s1){if(s==s1) return 1;else if(s[1]==s1[0]&&s[2]==s1[1]) return 2;else if(s[2]==s1[0]) return 3;return 4;}int main(){string sc[10][6]={{"QQQ","QQQ","QQQ","QQQ","QQQ","QQQ"},{"QQW","QWQ","WQQ","WQQ","WQQ","WQQ"},{"QQE","QEQ","EQQ","EQQ","EQQ","EQQ"},{"WWW","WWW","WWW","WWW","WWW","WWW"},{"QWW","WQW","WWQ","WWQ","WWQ","WWQ"},{"WWE","WEW","EWW","EWW","EWW","EWW"},{"EEE","EEE","EEE","EEE","EEE","EEE"},{"QEE","EQE","EEQ","EEQ","EEQ","EEQ"},{"WEE","EWE","EEW","EEW","EEW","EEW"},{"QWE","QEW","EQW","EWQ","WEQ","WQE"},};m['Y']=0; m['V']=1; m['G']=2; m['C']=3; m['X']=4;m['Z']=5; m['T']=6; m['F']=7; m['D']=8; m['B']=9;while(scanf("%s",str+1)!=EOF){int len=strlen(str+1);string s[6];s[0]=" ",s[1]=" ",s[2]=" ",s[3]=" ",s[4]=" ",s[5]=" ";for(int i=1;i<=len;i++){int x=m[str[i]];for(int j=0;j<6;j++){string ss=sc[x][j];dp[i][j]=inff;for(int k=0;k<6;k++)dp[i][j]=min(dp[i-1][k]+check(s[k],ss),dp[i][j]);}for(int j=0;j<6;j++) s[j]=sc[x][j];}ll ans=inff;for(int i=0;i<6;i++) ans=min(dp[len][i],ans);printf("%lld\n",ans);}}

原网站

版权声明
本文为[swust_fang]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/221/202208090700344248.html

边栏推荐

猜你喜欢

随机推荐