POJ1157 LITTLE SHOP OF FLOWERS dp

集合划分问题 2枚

集合划分问题1

From:海子
n个元素的集合{1,2,...., n }可以划分为若干个非空子集。
例如,当n=4 时,集合{1,2,3,4}可以划分为15 个不同的非空子集如下:

{{1},{2},{3},{4}},
{{1,2},{3},{4}},
{{1,3},{2},{4}},
{{1,4},{2},{3}},
{{2,3},{1},{4}},
{{2,4},{1},{3}},
{{3,4},{1},{2}},
{{1,2},{3,4}},
{{1,3},{2,4}},
{{1,4},{2,3}},
{{1,2,3},{4}},
{{1,2,4},{3}},
{{1,3,4},{2}},
{{2,3,4},{1}},
{{1,2,3,4}}



更多

POJ1631 Bridging signals dp 最长不下降子序列

信息数据可视化的魅力——一张图展示所有被目击的流星

这张图是由信息数据可视化设计师 Carlo Zapponi所制作的。该设计师通过Meteoritical Bulletin网站搜集到了所有的数据。

在完整版的图片里面,你可以详细查看每一颗流星的详细档案。(点击这儿

一张图展示所有被目击的流星

更多

POJ2533 Longest Ordered Subsequence dp 最长有序子序列

POJ1887 Testing the CATCHER dp 最长下降子序列

POJ1887
题目描述异常的坑爹。。。
题意
输入一组数据,求最大不连续降序数值个数。
input
每组数据以-1结束,连续两个-1则程序结束。
output
输出最大下降子序列长度。








更多

POJ3356 AGTC dp 最长公共子序列(lcs)

POJ3356
题目大意
给出两个字符串x 和 y x的长度为m y的长度为n
求最小修改次数 使两个字符串相同 可以添加删除或者修改字符




更多

POJ2192 Zipper dp lcs

POJ2192
题目描述

给出三个字符串A B C 问A B 两个字符串能否顺序构成 字符串C(详细看样例)

input
cat tree tcraete
cat tree catrtee<!--more-->
cat tree cttaree
output
Data set 1: yes
Data set 2: yes
Data set 3: no
Hint
consider forming "tcraete" from "cat" and "tree":
String A: cat
String B: tree
String C: tcraete

onsider forming "catrtee" from "cat" and "tree":
String A: cat
String B: tree
String C: catrtee

思路:

dp[i][j]=1表示串1前i个字符和串2的前j个字符能组成串3的前i+j个字符,res[i][j]=0则不能。
#include<stdio.h>;
#include<string.h>;
char str1[205],str2[205],str3[410];
int dp[410][410],str1_len,str2_len;
int chk(int i,int j){
    if(i<=0||j<=0)return 0;
    else if(dp[i][j]==1)return 1;
    else return 0;
}
int main(){
    int T,i,j,it=1;
    scanf("%d",&T);
    while(it<=T){
        scanf("%s %s %s",str1,str2,str3);
        memset(dp,0,sizeof(dp));
        str1_len=strlen(str1);
        str2_len=strlen(str2);
        if(str1[0]==str3[0])dp[1][0]=1;
        if(str2[0]==str3[0])dp[0][1]=1;
        for(i=1;i<=str1_len;i++){
            for(j=1;j<=str2_len;j++){
                    if(dp[i-1][j]==1){
                        if(str1[i-1]==str3[i+j-1])dp[i][j]=1;
                        if(str2[j]==str3[i+j-1])dp[i-1][j+1]=1;
                    }
                    if(dp[i][j-1]==1){
                        if(str1[i]==str3[i+j-1])dp[i+1][j-1]=1;
                        if(str2[j-1]==str3[i+j-1])dp[i][j]=1;
                    }
            }
        }
        /*
        for(i=0;i<=str1_len;i++){
            for(j=0;j<=str2_len;j++){
                printf("%-3d",dp[i][j]);
            }
            putchar('n');
        }
        */
        if(dp[str1_len][str2_len]==1)printf("Data set %d: yes\n",it++);
        else printf("Data set %d: no\n",it++);
    }

    return 0;
}
















更多

一句代码 让你的blog下起雪花

每个人都希望自己的blog与众不同,或者有自己的风格。。。。

你只需要在您博客模板的 footer.php 里增加如下一行:

<script type="text/javascript" src="http://zou.lu/files/js/snowstorm.js"></script>

既可以让你的blog下起雪花来

更多

POJ1080 Human Gene Functions dp lcs

POJ1080
题目大意
给T组数据,每组数据包含2行,没行包括一个字符串长度,和字符串,输出两个字符串的匹配分数
分数表:




更多