首页 > 代码库 > qscoj 喵哈哈村的打印机游戏 区间dp
qscoj 喵哈哈村的打印机游戏 区间dp
点这里去看题
区间dp ,dp[l][r][d]代表从l到r的区间底色为d,具体看代码
第一次见到区间dp。。。两个小时对着敲了五遍终于自己敲懂了一遍ac
#include<bits/stdc++.h> using namespace std; int dp[55][55][55]; string s; int solve(int l,int r,int d) { if(l>r)return 0; if(l==r&&s[l]-‘A‘==d)return dp[l][r][d]=0; if(l==r)return dp[l][r][d]=1; if(dp[l][r][d]!=-1)return dp[l][r][d]; dp[l][r][d]=1e8; for(int i=0;i<26;i++) dp[l][r][d]=min(dp[l][r][d],solve(l,r,i)+1); if(s[l]-‘A‘==d)dp[l][r][d]=min(dp[l][r][d],solve(l+1,r,d)); if(s[r]-‘A‘==d)dp[l][r][d]=min(dp[l][r][d],solve(l,r-1,d)); for(int i=l+1;i<r;i++) { if(s[i]-‘A‘==d) dp[l][r][d]=min(dp[l][r][d],solve(l,i-1,d)+solve(i+1,r,d)); } return dp[l][r][d]; } int main() { while(cin>>s) { memset(dp,-1,sizeof(dp)); cout<<solve(0,s.size()-1,27)<<endl; } return 0; }
qscoj 喵哈哈村的打印机游戏 区间dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。