codeforce 44E Anfisa the Monkey(기억 검색)

1558 단어
제목:
직렬을 제시하고 k분으로 나누어야 하며 각 직분의 길이는 [a, b] 사이에서 실행 가능한 방안을 구한다.
문제 풀이:
검색 문제, 직접 검색 시간 초과, dp로 지나간 상황을 저장합니다.dp[i][j]는 전 i개의 점을 표시하고 j개의 집합이 지나갔는지 여부를 나눈다.
#include<iostream>
#include<math.h>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
const int oo=0x3f3f3f3f;
const ll OO=1LL<<61;
const int maxn=205;
int n,m,a,b;
int mark[maxn];
int dp[maxn][maxn];
char str[maxn];

void output()
{
    mark[0]=0;
    for(int i=1;i<=m;i++)
    {
        for(int j=mark[i-1]+1;j<=mark[i];j++)
            printf("%c",str[j]);
        puts("");
    }
}

bool dfs(int cur,int k)
{
    if(dp[cur][k])
        return false;
    if(k==m&&cur==n)
    {
        output();
        return true;
    }
    if(k>m)
    {
        return false;
    }
    if(cur>n)
    {
        return false;
    }
    for(int i=cur+1;i<=n;i++)
    {
        if(a<=i-cur&&i-cur<=b)
        {
            mark[k+1]=i;
            if(dfs(i,k+1))
                return true;
            else
                dp[i][k+1]=1;
        }
    }
    return false;
}

int main()
{
    while(scanf("%d %d %d",&m,&a,&b)!=EOF)
    {
        memset(dp,0,sizeof dp);
        scanf("%s",str+1);
        n=strlen(str+1);
        if(!dfs(0,0))
            printf("No solution
"); } return 0; } /** 3 2 5 abrakadabra 4 1 2 abrakadabra */

좋은 웹페이지 즐겨찾기