大家好，欢迎来到IT知识分享网。
题目描述
LHX教主要来X市指导OI学习工作了。为了迎接教主，在一条道路旁，一群Orz教主er穿着文化衫站在道路两旁迎接教主，每件文化衫上都印着大字。一旁的Orzer依次摆出“欢迎欢迎欢迎欢迎……”的大字，但是领队突然发现，另一旁穿着“教”和“主”字文化衫的Orzer却不太和谐。
为了简单描述这个不和谐的队列，我们用“jjj”替代“教”，“zzz”替代“主”。而一个“jjj”与“zzz”组成的序列则可以描述当前的队列。为了让教主看得尽量舒服，你必须调整队列，使得“jzjzjz”子串尽量多。每次调整你可以交换任意位置上的两个人，也就是序列中任意位置上的两个字母。而因为教主马上就来了，时间仅够最多作KKK次调整（当然可以调整不满KKK次），所以这个问题交给了你。
输入输出格式
输入格式：
第一行包含222个正整数NNN与KKK，表示了序列长度与最多交换次数。
第二行包含了一个长度为NNN的字符串，字符串仅由字母“jjj”与字母“zzz”组成，描述了这个序列。
输出格式：
一个非负整数，为调整最多KKK次后最后最多能出现多少个“jz”子串。
输入输出样例
说明
【样例说明】
第111次交换位置111上的zzz和位置444上的jjj，变为jzzzjjzzzjjzzzj；
第222次交换位置444上的zzz和位置555上的jjj，变为jzzjzjzzjzjzzjz。
最后的串有222个“jzjzjz”子串。
【数据规模与约定】
对于10%10\%10%的数据，有N≤10N≤10N≤10；
对于30%30\%30%的数据，有K≤10K≤10K≤10；
对于40%40\%40%的数据，有N≤50N≤50N≤50；
对于100%100\%100%的数据，有N≤500,K≤100N≤500,K≤100N≤500,K≤100。
wori ，dp 的题目咋还是“贪心”的标签。。
而且还是一个比较巧妙有难度的dp;
有一个明显的地方是：我们可以把交换看作为 j->z,z->j;
那么我们用： dp[ i ][ j ][ k ]表示前 i 个字母中，j个 ‘j’变成了 ‘z’, k 个’z’变为 ‘j’时的最大值；
转移方程讨论一下；
#include<iostream> #include<cstdio> #include<algorithm> #include<cstdlib> #include<cstring> #include<string> #include<cmath> #include<map> #include<set> #include<vector> #include<queue> #include<bitset> #include<ctime> #include<deque> #include<stack> #include<functional> #include<sstream> //#include<cctype> //#pragma GCC optimize(2) using namespace std; #define maxn #define inf 0x7fffffff //#define INF 1e18 #define rdint(x) scanf("%d",&x) #define rdllt(x) scanf("%lld",&x) #define rdult(x) scanf("%lu",&x) #define rdlf(x) scanf("%lf",&x) #define rdstr(x) scanf("%s",x) typedef long long ll; typedef unsigned long long ull; typedef unsigned int U; #define ms(x) memset((x),0,sizeof(x)) const long long int mod = 1e9 + 7; #define Mod #define sq(x) (x)*(x) #define eps 1e-3 typedef pair<int, int> pii; #define pi acos(-1.0) //const int N = 1005; #define REP(i,n) for(int i=0;i<(n);i++) typedef pair<int, int> pii; inline ll rd() { ll x = 0; char c = getchar(); bool f = false; while (!isdigit(c)) { if (c == '-') f = true; c = getchar(); } while (isdigit(c)) { x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); } return f ? -x : x; } ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a%b); } int sqr(int x) { return x * x; } /*ll ans; ll exgcd(ll a, ll b, ll &x, ll &y) { if (!b) { x = 1; y = 0; return a; } ans = exgcd(b, a%b, x, y); ll t = x; x = y; y = t - a / b * y; return ans; } */ int n, m; char s[maxn]; int dp[503][200][200]; int main() { //ios::sync_with_stdio(0); cin >> n >> m; rdstr(s + 1); memset(dp, ~0x3f, sizeof(dp)); dp[0][0][0] = dp[1][0][0] = dp[1][s[1] == 'j'][s[1] == 'z'] = 0; for (int i = 2; i <= n; i++) { for (int j = 0; j <= m; j++) { for (int k = 0; k <= m; k++) { dp[i][j][k] = dp[i - 1][j][k]; if (s[i] == 'z'&&s[i - 1] == 'j') { dp[i][j][k] = max(dp[i][j][k], dp[i - 2][j][k] + 1); } if (k&&s[i] == 'z'&&s[i - 1] == 'z') { dp[i][j][k] = max(dp[i][j][k], dp[i - 2][j][k - 1] + 1); } if (j&&s[i] == 'j'&&s[i - 1] == 'j') { dp[i][j][k] = max(dp[i][j][k], dp[i - 2][j - 1][k] + 1); } if (j&&k&&s[i] == 'j'&&s[i - 1] == 'z') { dp[i][j][k] = max(dp[i][j][k], dp[i - 2][j - 1][k - 1] + 1); } } } } int maxx = -inf; for (int i = 0; i <= m; i++) { maxx = max(maxx, dp[n][i][i]); } cout << maxx << endl; return 0; }
转载于:https://www.cnblogs.com/zxyqzy/p/10253689.html
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/121424.html
