喜欢的话就坚持吧

9月 14

发表于 • 219 views • 没有评论,快来呀!

数据结构,树链剖分

题目大意

给定一棵有n个节点的无根树和m个操作，操作有2类：
1、将节点a到节点b路径上所有点都染成颜色c；
2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），如“112221”由3段组成：“11”、“222”和“1”。
请你写一个程序依次完成这m个操作。

继续阅读

阅读全文 >>

9月 05

发表于 • 125 views • 没有评论,快来呀!

动态规划

题目大意：

给你一个串s和一些单词，要求你把串分成k段，使每段所含单词数之和最大。
要求单个字母只能对应一个单词的开头，要求单个字母只能对应一个单词的开头，
如 串为：funk
单词为fun ,funk
你就只能选一个匹配

数据范围 len(s)<=200 只有小写字母 k<=40数据范围 len(s)<=200 只有小写字母 k<=40

由于范围很小，各种hash暴力贪心花式kmp都能过，


这里讲一种dp的思路，
设f[i][j]为考虑到第i位后面的空，已经断成了j块的最多匹配。
感觉和上道[乘积最大]很像
转移也是枚举上次从哪断掉
所以现在差的就是如何找出匹配的单词数
我们可以开一个数组d[i]表示以位置为i的字符开头匹配的结尾位置
由于我们要最多，d[i]显然要取最小
~~~~如刚才的 fuck（划掉）
如刚才的funk，d[1]就是3（和fun匹配而不是funk）
然后我们预处理出d数组，每次转移看有几个d是可行的，
记为tot进行转移就行。
（算了算了解释不清看代码就行）

f_{i,j}=max(f_{k,j-1}+tot)

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;
const int N=205;
const int M=11;
const int INF=0x3f3f3f3f;

char s[N],word[M][N],len[M];
int p,m,n,num;
int d[N],f[N][M<<2];

void dp()
{
//先处理出d数组
    memset(d,INF,sizeof(d));
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=num;++j)
        {
            if(n-i+1<len[j]||d[i]<=len[j]) continue;
            //如果过长或不优都不要
            bool flag=false;
            for(int k=0;k<len[j];++k)
                if(s[i+k]!=word[j][k+1]) {flag=true;break;}//暴力匹配即可
                //或者闲的无聊写个trie树把常数优化掉
            if(flag) continue;
            d[i]=i+len[j]-1;
        }
       // printf("d[%d]=%dn",i,d[i]);
    }
    //进行dp
    for(int i=1;i<=n;++i)//首先枚举位置
        for(int j=1;j<=m;++j)//其次枚举断了几处
        {
            int tot=0;
            for(int k=i;k>=j;--k)//然后在哪里断的，反向转移保证tot合法
            {
                if(d[k]<=i) tot++;
                f[i][j]=max(f[i][j],f[k-1][j-1]+tot);
            }
        }
}
int main()
{
    scanf("%d%d",&p,&m);
    for(int i=1;i<=p;i++) scanf("%s",s+1+20*(i-1));
    n=strlen(s+1);
    //首先这题的垃圾输入方式非常毒瘤
//    printf("%s",s+1);//return 0;
    scanf("%d",&num);
    for(int i=1;i<=num;i++) 
    scanf("%s",word[i]+1),len[i]=strlen(word[i]+1);
    //其次你读入每个单词
    dp();
    printf("%d",f[n][m]);
}

阅读全文 >>

«12345 »