亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

uva 10069 Distinct Subsequences(高精度 + DP

系統 1961 0

題目連接:10069 - Distinct Subsequences


題目大意:給出兩個字符串x (lenth < 10000), z (lenth < 100), 求在x中有多少個z。


解題思路:二維數組DP, 有類似于求解最長公共子序列, cnt[i][j]表示在x的前j個字符中有多少個z 前i個字符。

狀態轉移方程 ?

1、x[j] != z[i] ? ? ? ? ? ? ?cnt[i][j] = cnt[i][j - 1];

2、x[j] == z[i] ? cnt[i][j] = cnt[i][j - 1] + cnt[i - 1][j - 1];

計算的時候使用高精度, 并且要見j == 0的情況歸1, i == 0 的情況歸0。


?

    #include <stdio.h>

#include <string.h>

#include <iostream>

using namespace std;

const int N = 10005;

const int M = 105;



struct bign {

    int len, sex;

    int s[M];



    bign() {

	this -> len = 1;

	this -> sex = 0;

	memset(s, 0, sizeof(s));

    }



    bign operator = (const char *number) {

	int begin = 0;

	len = 0;

	sex = 1;

	if (number[begin] == '-') {

	    sex = -1;

	    begin++;

	}

	else if (number[begin] == '+')

	    begin++;



	for (int j = begin; number[j]; j++)

	    s[len++] = number[j] - '0';

    }



    bign operator = (int number) {

	char string[N];

	sprintf(string, "%d", number);

	*this = string;

	return *this;

    }



    bign (int number) {*this = number;}

    bign (const char* number) {*this = number;}



    bign change(bign cur) {

	bign now;

	now = cur;

	for (int i = 0; i < cur.len; i++)

	    now.s[i] = cur.s[cur.len - i - 1];

	return now;

    }



    void delZore() {	// 刪除前導0.

	bign now = change(*this);

	while (now.s[now.len - 1] == 0 && now.len > 1) {

	    now.len--;

	}

	*this = change(now);

    }



    void put() {    // 輸出數值。

	delZore();

	if (sex < 0 && (len != 1 || s[0] != 0))

	    cout << "-";

	for (int i = 0; i < len; i++)

	    cout << s[i];

    }



    bign operator + (const bign &cur){  

	bign sum, a, b;  

	sum.len = 0;

	a = a.change(*this);

	b = b.change(cur);



	for (int i = 0, g = 0; g || i < a.len || i < b.len; i++){  

	    int x = g;  

	    if (i < a.len) x += a.s[i];  

	    if (i < b.len) x += b.s[i];  

	    sum.s[sum.len++] = x % 10;  

	    g = x / 10;  

	}  

	return sum.change(sum);  

    } 

};



bign cnt[M][N], sum;

char x[N], z[M];



int main() {

    int cas;

    scanf("%d", &cas);

    while (cas--) {

	scanf("%s%s", x, z);

	int n = strlen(x), m = strlen(z);

	for (int i = 0; i <= n; i++)

	    cnt[0][i] = 1;



	for (int i = 1; i <= m; i++) {

	    cnt[i][0] = 0;

	    for (int j = 1; j <= n; j++) {

		cnt[i][j] = cnt[i][j - 1];

		if (z[i - 1] == x[j - 1])   

		    cnt[i][j] = cnt[i][j] + cnt[i - 1][j - 1];

	    }

	}

	cnt[m][n].put();

	printf("\n");

    }

    return 0;

}


  


?

?

uva 10069 Distinct Subsequences(高精度 + DP求解子串個數)


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦?。。?/p>

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 精品久久久久亚洲 | 亚洲精品精品 | 免费看久久 | 欧美性猛交ⅹxxx乱大交免费 | 欧美一区二区三区在线可观看 | 国产99视频精品免视看9 | 在线观看一区二区精品视频 | 天天做天天爱天天爽天天综合 | 不卡国产| 久久这里只有精品视频99 | 国产99久久精品 | 久久www免费人成_看 | 香蕉久久综合精品首页 | 国产区综合 | 伊人久久一本 | 国产精品高清在线 | 婷婷夜夜躁天天躁人人躁 | 精品国产视频在线观看 | 狠狠色丁香久久婷婷综合_中 | 日本一区二区三区高清福利视频 | 爱爱永久免费视频网站 | 欧美激情_区二区三区 | 99久久精品6在线播放 | 婷婷色在线观看 | 77奇米影视 | 91人人看 | 久青草影院在线观看国产 | 在线a毛片免费视频观看 | 久艹视频在线 | 日本一区二区三区高清在线观看 | 久久97久久97精品免视看清纯 | 香蕉超级碰碰碰97视频蜜芽 | 亚欧成人在线 | 成人亚洲视频 | 一级毛片免费播放 | 日日夜夜视频 | 夜夜撸日日干 | 男女一级免费视频 | 久久99精品久久久久久臀蜜桃 | 久久99精品国产麻豆婷婷 | 欧美综合成人 |