本文主要是介绍P1025 数的划分 我好想穿小裙子啊!!!! + 相似基因,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
本来想写的,后来搁置了
后来在信息安全课上摸鱼(一直在写字老师还以为我在认真听课hhhhh)
结果那天晚上要交作业耽误了直到今天hhh重新捡起来 瞎继而写。。。
样例错了 瞎继而改100 5
看呀看 看呀看 改了竟然对了。。。神奇的操作
其实不难的 但是~ 需要一点思考量这样子
毕竟11.7k人做出来呢
普及的题 还是要想想想想想想然后就想出来了~
继续加油啦啦啦
#include<iostream>
using namespace std;
typedef long long ll;
ll f[205][10];
ll dp(ll oral, ll j,ll yet) {//j是块数...//a是最开始要求要操作的数//fa是上一个...ll sum = 0;if (j == 3) {for (int i = 1; i <= oral / 3; i++) {if (i < yet)//以防2 1 2 2 这种事情发生 小鱼的不行 只能等于!!!continue;else if (i * 3 > oral)//以防3 2 2 这种事情发生 直接停止吧break;else {if (f[oral - i][2] - i + 1 < 0)continue;else sum += f[oral - i][2] - i + 1;}}}else { //比如 8 4块这种请求啦 for (int i = 1; i <= oral/j; i++) {if (i < yet)//以防2 1 2 2 这种事情发生 小鱼的不行 只能等于!!!continue;else if (i * j > oral)//以防3 2 2 这种事情发生 直接停止吧break;sum += dp(oral - i, j - 1, i);}}return sum;
}//2000!!!------------
int main() {ll number, times;cin >> number >> times;for (int i = 1; i <= 205; i++) {f[i][2] = i / 2;}if(times!=2)cout<<dp(number, times,1)<<endl;else cout << f[number][2]<<endl;//cout << sum << endl;return 0;
}
-----------(之前写的)
相似基因:过题代码看前面吧。
其实也还就是最长公共子序列的加了一点东西,唔,加了一点诸如怎么匹配的问题,完全了解前文的匹配过程(只关注当前 Hi~?o(* ̄▽ ̄*)ブ)就可以
哇~ 过题人那么多。
后来啊啊还是~还是桂花课上用手重新写了一遍发现有初始化的时候没值,只能从0 0开始这是不行的
后来20分。。 后来写了AAT TAA来实验
发现不能取得max的,因为AAANSLKD
AAAKOPXKPSNA 总不能最大的 是15吧 要取最后而不是取最大……
(所以每一步在干嘛,LCS倒是有可能因为最大的只能取得一次啊……)
【所以说还是静下来用心去做~】
【静下来……真的能认真去做吗?】
普及-的题卡了三天还行。还好继续没看题解只是确定了一下正确思路(因为杂项太多了我以前想的有正解的一种然后被淹没了……)
--------------------
//啊!memset在cstring里面!!!!
/*
又。。。。这个还是看了题解,我感觉最开始卡到我的关键在于~
对之前的lcs不够了解。然后一旦你开始乱七八糟搞什么flag位啊在动态规划里一般你已经死了-。-
就是呢,QAQ如果匹配过了也没有关系,因为匹配的是[i-1][j-1]啊 若它已经匹配过一次了需要重新匹配说明在
在扔掉当前i和当前j的前提下前面也有匹配的 gtt gtett 这样a1[3] a2[5]匹配的时候担心 T 已经用过了?没事 T 只有一个
哪怕你下面怎么样 上面匹配的是a[2]之前的 最大的还只能是3.。。
想法其实是对的。。理解的不深刻 导致后面还是乱了啊-。-(后面还是被自己欺骗了
长长的一串 相当于每一次都是斜着更新的 我后面变成什么样子了完全依赖于前面一点点的慢慢的更新
*/
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
using namespace std;
int a1[105];
int a2[105];
int dp1[105];
int dp2[105];
int dp[105][105];
int sum[105][105];
int c[10][10];
void init() {c[1][2] = c[2][1] = c[4][1] = c[1][4] = c[5][4] = c[4][5] = -1;c[3][1] = c[1][3] = c[4][2] = c[2][4] = c[4][3] = c[3][4] = c[5][3] = c[3][5] = -2;c[3][2] = c[2][3] = c[5][1]=c[1][5]=-3;c[2][5] = c[5][2] = -4;
}
int main() {init();int n1, n2; string s1, s2; cin >> n1 >> s1; cin >> n2 >> s2;s1 = "#" + s1;s2 = "E" + s2;for (int i = 1; i <=n1 ; i++) {if (s1[i] == 'A')a1[i] = 1;else if (s1[i] == 'C')a1[i] = 2;else if (s1[i] == 'G')a1[i] = 3;else if (s1[i] == 'T')a1[i] = 4;}for (int i = 1; i <=n2; i++) {if (s2[i] == 'A')a2[i] = 1;else if (s2[i] == 'C')a2[i] = 2;else if (s2[i] == 'G')a2[i] = 3;else if (s2[i] == 'T')a2[i] = 4;}for (int i = 1; i <= max(n1, n2); i++) {for (int j = 1; j <= max(n1, n2); j++) {sum[i][j] = -9999;}}sum[0][0] = 0;for (int i = 1; i <= n1; i++) {sum[i][0] = sum[i - 1][0] + c[5][a1[i]];//这个就是i已经去和空的配对了//不然初始化有误差}for (int j = 1; j <= n2; j++) {sum[0][j] = sum[0][j - 1] + c[5][a2[j]];}int maxx = 0; int maxs = 0;for (int i = 1; i <= n1; i++) {//sum[i][0] = sum[i - 1][0] + c[a1[i]][5];//sum[0][0] = 0;for (int j = 1; j <= n2; j++){if (a1[i] == a2[j]) {dp[i][j] = dp[i - 1][j - 1] + 1;sum[i][j] = sum[i - 1][j - 1] + 5;}else {/*//不等的话,就是谁对应空格,或者两个直接对应。int temp1 = 0; sum[i - 1][j] + c[a1[i - 1]][5];int temp2 = 0; int temp3 = 0;if (a1[i]==a2[j-1])temp2= sum[i][j - 1] + c[5][a2[j]];//我家的上家和你配对了,那好吧我先单着//else if (a1[i - 1] == a2[j])temp1 = sum[i - 1][j] + c[a1[i]][5];else if (a1[i] != a2[j])temp3 = sum[i - 1][j - 1] + max(c[a1[i]][a2[j]],max(c[a1[5]][a2[j]], c[a1[i]][a2[5]]));else if(i!=1&&j!=1&&sum[i-2][j-2]==sum[i-1][j-1]+5)temp1 = sum[i - 1][j] + c[a1[i]][5];//相等的不算啊,如果上一家真的结亲了//。。。 什么啊 a1[i] 和a2[j] 肯定就已经是不相等了//什么啊。。这已经是最下的下策了 我们如果我们的前面都不相等只好我们两个凑一对儿//或者,你是空的,我也是空的。。*///只看当下的决策?//if (flag == j - 1) {//正好是在前面匹配的,那抱歉没办法了再见你只能单着了// sum[i][j] += sum[i][j - 1] + c[5][a2[j]];//我们硬要匹配好,还是各自纷飞好?sum[i][j]= max(sum[i - 1][j - 1] + c[a1[i]][a2[j]],max(sum[i-1][j]+ c[5][a1[i]],sum[i][j-1]+ c[5][a2[j]]));//sum[i][j] = max(ms,sum[i][j]);dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}maxx = max(dp[i][j], maxx);
// maxs = max(maxs, sum[i][j]);}}//cout << maxx << endl;cout << sum[n1][n2] << endl;return 0;
}
-------------结尾1! 我的手机被抽特王收走了~!!!!!我只能!!!!!
这篇关于P1025 数的划分 我好想穿小裙子啊!!!! + 相似基因的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!