[洛谷 P2679]子串

danihao123 posted @ 2016年8月12日 17:40 in 题解 with tags 动态规划 NOIP 洛谷 , 633 阅读
转载请注明出处:http://danihao123.is-programmer.com/

DP神题……

第一眼都能看出来是DP,然后大约构思就出来了,但细节很复杂啊……

看完第一眼后大家大约都能想出来[tex]d[i][j][k][/tex]这样的状态,但是注意[tex]A[i]=B[j][/tex](字符数组细节此处未予考虑)的情况和整体情况要独立对待,否则这题只能233

然后下面就不难想了。但是注意直接开数组会233,要开滚动数组防MLE。

代码:

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=1001,maxm=201,maxk=201;
const int MOD=1e9+7;
int d[2][maxm][maxk][2];
char A[maxn];
char B[maxm];
int main(){
    register int i,j,p,now,pre;
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    scanf("%s%s",A,B);
    d[0][0][0][1]=1;
    for(i=1;i<=n;i++){
        now=i%2;
        pre=1-now;
        d[now][0][0][1]=1;
        for(j=1;j<=m;j++){
            if(A[i-1]==B[j-1])
                for(p=1;p<=min(k,j);p++){
                    d[now][j][p][0]=(d[pre][j-1][p][0]+d[pre][j-1][p-1][1])%MOD;
                    d[now][j][p][1]=(d[pre][j][p][1]+d[now][j][p][0])%MOD;
                }
            else
                for(p=1;p<=min(k,j);p++){
                    d[now][j][p][0]=0;
                    d[now][j][p][1]=d[pre][j][p][1];
                }
        }
    }
    printf("%d\n",d[n%2][m][k][1]);
    return 0;
}
Delete Instagram Cha 说:
Dec 20, 2022 10:32:59 PM

You may be asking how to delete Instagram messages because you want to clear up your inbox of spam messages. Perhaps your need to erase texts is a reflex reaction to an emotionally charged scenario. Delete Instagram Chat There are both good and negative reasons to delete your conversations and bear in mind that this is a final decision, so make it carefully. Here’s all you need to know about erasing or deleting Instagram direct messages.

cmbihar.in 说:
Jul 03, 2023 11:23:56 AM

Initiative of professional writers who have come together for dedicated news coverage of latest happenings around the country (India). Our team comprises of professional writers & citizen journalists with diverse range of interest in Journalism who are passionate about cmbihar.in publishing the Education Updates with transparency in general public interest


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter