Gym 101669A Concerts DP

1269 단어 #동적 기획
n,k를 정하다.26개수.두 꿰미를 주다.첫 번째 sk열은 얻을 열이고 두 번째 열은 모열이다.모열에서 몇 종류의 sk열을 일치시킬 수 있는지 구하십시오.[요구: 일부 특정 자모는 선택한 후에 몇 개의 간격을 두어야 다음을 선택할 수 있다].
답안%1e9+7;
분명히 DP였어. 시합할 때 내가 못했어.
사실 이 문제의 모형도 두 사람 관계에 인접한 DP임이 분명하다.하지만 간격을 두는 문제를 넣으면 안 할 거야...
문제를 푸는 데는 먼저 모형을 간소화하고 먼저 자신이 배운 모형에 기대야 한다.
pp[i][j]i는 모열의 위치를 나타내고, j는 자열(sk열)의 위치를 나타낸다.
가장 바깥쪽 순환은 서브열에 있는 위치를 정하고 안쪽 순환은 답안에 맞는 상황을 벗어나 답안을 같은 위치에 부여한다.
#include 
#define ms(x) memset(x, 0, sizeof(x))
#define ll long long
using namespace std;
const int N = 1123;
const int mod = 1e9+7;
const int maxN = 100005, maxK = 310;
int dp[maxN][maxK];
int dis[30];
int n, k;
char sn[maxN], sk[maxK];
int main(){
    scanf("%d%d", &k,&n);
    for(int i=0;i<26;i++){
        scanf("%lld", &dis[i]);
    }
    scanf("%s",sk+1);
    scanf("%s",sn+1);
    ms(dp);
    dp[0][0] = 1;
    for(int tk=1;tk<=k;tk++){
        int index = 0;
        ll now  = 0;
        int cha = (tk==1)?0:dis[sk[tk-1]-'A'];
        for(int i=1;i<=n;i++){
            while(index+cha

좋은 웹페이지 즐겨찾기