서열형 동적 기획-수수께끼 맞추기(3교 연합시험 문제)

[문제 설명]
최소한의 더하기 또는 곱하기 기호를 삽입하여 숫자 문자열의 연산 결과를 T로 만들려면 길이가 N인 숫자 문자열과 숫자 T를 제시합니다.연산자*호의 우선순위는 +호보다 높고 연산수는 임의의 전도 0이 있을 수 있다.
[형식 입력]
다섯 조의 데이터를 초과하지 않고 한 조의 데이터 두 줄을 입력하세요.각 그룹의 데이터의 첫 번째 행위 길이 N은 0~9의 숫자 문자열만 포함한다.두 번째 동작은 숫자 T입니다.T<0 을 입력하면 입력이 끝납니다.
[출력 형식]
한 개의 숫자가 단독으로 한 줄을 차지하여 최소한 추가해야 하는 연산자(+호 또는 *호)의 수를 나타낸다.
[샘플 입력]
032089 5 333 9 00 -1
[샘플 내보내기]
3 2
[데이터 범위]
30% 데이터의 경우 1<=N<=10,0<=T<=50.50%의 데이터에 대해 1<=N<=15,0<=T<=200.모든 데이터에 대해 1<=N<=20,0<=T<=300이 있습니다.
보기만 해도 징그러운 제목: 우선순위>+이기 때문에 연결된 연속 숫자를 한 조로 보고 조를 나누어 움직일 수 있다.상태 방정식: f[i][j]는 이전 i개의 숫자와 j를 표시하고 추가된 연산자의 최소 개수 f[i][j]=min{f[k][x]+1+g[k+1][i][j-x]|1<=k=0} 경계: f[i][j]=g[1][i][j]
g[i][j][x]는 i~j개의 숫자 사이에 *를 삽입하고 x의 최소 삽입값 g[i][j][x]=min{g[i][p][k/num[p+1][j]]+1|k%num[p+1][j]==0}경계: g[i][j][num[j]]=0|num[i][j]][j]]][j]<=T
num[i][j]는 제i~j개의 숫자가 하나의 새로운 숫자를 구성하는 것을 나타낸다. (전도 0이 있을 수 있다)num[i][j]=num[i][j-1]+s[j]-'0'
문제점 발견: 1.num수조에서 i=i를 보증하는 것 같으면 문제없고, 코드에서num[i][j]=max(0,num[i][j-1])*10+s[j]-'0'을 사용하지 않았다).num[i][j]는 >long long일 수 있지만 어쩔 수 없다. 마이너스지만 만족하는 것도 없을 것이다. 왜냐하면 T<=300이기 때문이다. 그러나 g[i][j][num[i][j]]=0을 판단하는 조건은if(num[i][j]<=T&num[i][j]>=0)이다.
2. 얼마나 큰 값으로 순환하는지 주의해야 한다.
3. f[i][j]의 경계는 간단한 inf가 아니라 g[1][i][j]이다. 만약에 inf를 부여하면 답은 -1이다.
4. g[i][j][0]에 대한 질문은 코드에 쓰여 있고 오래 걸렸습니다.
코드는 다음과 같습니다.

#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int maxn=25;
const int inf=100000000;
const int maxm=305;
int T,f[maxn][maxm],n,g[maxn][maxn][maxm];
char s[maxn];
int num[maxn][maxn];
void db()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int k=1;k<=T;k++) cout<' ';
            cout<cout</*
    f[i][j]   i     j      
    f[i][j]=min{ f[k][x]+1+g[k+1][i][j-x] | 1<=k=0}
      ：f[i][j]=g[1][i][j]

    g[i][j][k]   *  i~j          k      
    g[i][j][k]=min{ g[i][p][k/num[p+1][j]] +1 | k%num[p+1][j]==0}
        g[i][j][0]           %0
      ：g[i][j][num[i][j]]=0  |num[i][j]<=T 
*/

void dp()
{
    for(int i=1;i<=n;i++)
    for(int j=i;j<=n;j++)
    {
        for(int k=0;k<=T;k++) g[i][j][k]=inf;
        if(num[i][j]<=T && num[i][j]>=0) g[i][j][num[i][j]]=0;//        LL    ，    
    }

    for(int i=1;i<=n;i++)
    for(int j=i;j<=n;j++)
    {
        if(num[i][j]==0) g[i][j][0]=0;
        else 
        {
            if(num[i][i]==0 || num[j][j]==0) g[i][j][0]=min(g[i][j][0],1);
            else
            {
                for(int p=i+1;p0]=min(g[i][j][0],g[i][p][0]+1); 
            }
        }
        for(int k=1;k<=T;k++)
        {
            for(int p=i;pif(num[p+1][j]>0 && k%num[p+1][j]==0)
            {
                g[i][j][k]=min(g[i][p][k/num[p+1][j]]+1,g[i][j][k]);
            }
        }
    }


    for(int i=1;i<=n;i++)
    for(int j=0;j<=T;j++) f[i][j]=inf;

    for(int i=1;i<=n;i++)
    for(int j=0;j<=T;j++)
    {
        int t=f[i][j];
        for(int k=1;kfor(int x=0;x<=j;x++) t=min(t,f[k][x]+1+g[k+1][i][j-x]);
        f[i][j]=t;
    }

//  db();
}
int main()
{
    freopen("in.txt","r",stdin);
//  freopen("out.txt","w",stdout); 
    while(scanf("%s",s+1)!=EOF)
    {
        n=strlen(s+1);
        memset(num,-1,sizeof(num));
        scanf("%d",&T);
        if(T<0) break;
        for(int i=1;i<=n;i++)
        {
            num[i][i-1]=0;
            for(int j=i;j<=n;j++) 
            {
                num[i][j]=num[i][j-1]*10+s[j]-'0';
                if(num[i][j]>T) break;
            }
        }
        dp();
        if(f[n][T]printf("%d
",f[n][T]);
        else printf("-1
");
    }

    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

01 가방, 완전 가방, 다중 가방 dp(동적 기획 입문 dp)

01 가방은 2진법으로 직접 표시할 수 있지만 데이터 양이 너무 많으면 시간을 초과하는 것이 폭력이다.01 가방의 사상은 바로 이 물품에 대해 내가 넣은 가치가 큰지 안 넣은 가치가 큰지 비교하여 방정식 f[i][v...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

서열형 동적 기획-수수께끼 맞추기(3교 연합시험 문제)

좋은 웹페이지 즐겨찾기