Invoker 2019CCPC秦皇岛站I题 2019-09-28 算法竞赛 暂无评论 59 次阅读 # Invoker 2019CCPC秦皇岛站I题（hdu重现赛） 题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=6739](http://acm.hdu.edu.cn/showproblem.php?pid=6739)  ## 思路 Y: QQQ (1) C: WWW(2) T: EEE(3) V: QQW (4) __ QWQ(5) __ WQQ(6) G: QQE (7) __ QEQ (8) __ EQQ(9) X: WWQ (10) __ WQW(11)__ QWW(12) Z: WWE(13) __ WEW (14)__ EWW(15) F: EEQ (16) __ EQE (17)__ QEE(18) D: EEW (19) __ EWE(20) __ WEE(21) B: QWE(22)__ QEW(23)__ WQE(24)__ WEQ(25)__ EWQ(26)__ EQW(27) 每个技能对应的法球（即按键）序列如上，总共有27种状态。 设技能序列长度为n 因为每发一个技能都要按一个R,而且法球的状态不改变，所以一定有n个R； 不算R ,设dp[ i ] [ j ] 表示 完成前 i 个技能 且 完成后为第 j 个状态的最少按键数（1<= j <= 27); 设 solve(k,j) 表示从第k 个状态 变成第 j 个状态所需的最小按键数， 例如， solve(1,4) = 1 ( QQQ(1) -- > QQW(4) ) dp[ i ] [ j ] = min ( dp[ i-1 ] [ k ]+solve(k,j) ) (1<=k<=27) 最后答案为ans = n + max ( dp[ n ] [ j ] ) (1<=j<=27) ## 代码 ```c++ #include<bits/stdc++.h> using namespace std; const int N=1e5+10; const int m=1061109567; char s[N]; int dp[N][30]; char a[28][3]= {{'0','0','0'},{'Q','Q','Q'},{'W','W','W'},{'E','E','E'},{'Q','Q','W',},{'Q','W','Q'},{'W','Q','Q'},{'Q','Q','E'},{'Q','E','Q'}, {'E','Q','Q'},{'W','W','Q'},{'W','Q','W'},{'Q','W','W'},{'W','W','E'},{'W','E','W'},{'E','W','W'},{'E','E','Q'},{'E','Q','E'},{'Q','E','E'}, {'E','E','W'},{'E','W','E'},{'W','E','E'},{'Q','W','E'},{'Q','E','W'},{'W','Q','E'},{'W','E','Q'},{'E','W','Q'},{'E','Q','W'}}; int solve(int x,int y) { if(a[x][0]==a[y][0]&&a[x][1]==a[y][1]&&a[x][2]==a[y][2]) return 0; else if(a[x][1]==a[y][0]&&a[x][2]==a[y][1]) return 1; else if(a[x][2]==a[y][0]) return 2; else return 3; } void shift(int i,int k) { for(int j=1; j<=27; j++) { if(dp[i-1][j]<m ) dp[i][k]=min(dp[i][k],dp[i-1][j]+solve(j,k)); } } int main() { std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); while(cin>>s+1) { int n=strlen(s+1); memset(dp,0x3f,sizeof(dp)); for(int i=1;i<=27;i++) dp[0][i]=3; for(int i=1; i<=n; i++) { if(s[i]=='Y') shift(i,1); if(s[i]=='C') shift(i,2); if(s[i]=='T') shift(i,3); if(s[i]=='V') { shift(i,4);shift(i,5);shift(i,6); } if(s[i]=='G') { shift(i,7);shift(i,8);shift(i,9); } if(s[i]=='X') { shift(i,10);shift(i,11);shift(i,12); } if(s[i]=='Z') { shift(i,13);shift(i,14);shift(i,15); } if(s[i]=='F') { shift(i,16);shift(i,17);shift(i,18); } if(s[i]=='D') { shift(i,19);shift(i,20);shift(i,21); } if(s[i]=='B') { shift(i,22);shift(i,23);shift(i,24);shift(i,25);shift(i,26);shift(i,27); } } int ans=99999999; for(int i=1; i<=27; i++) { ans=min(ans,dp[n][i]); } cout<<ans+n<<endl; } } ``` 标签: 算法 本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
评论已关闭