Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

为何RE?

Posted by zhanglanqing at 2016-03-15 21:23:28 on Problem 3280
#include<stdio.h>
#include<iostream>
#include<algorithm>
#define N 2000+3
#define M 58
using namespace std;
int n,m;
char s[N];
char at(int i){//变成从1开始的索引
    return s[i-1];
}

int dp[N][N];
int del[M];
int add[M];

void Init(){
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            dp[i][j]=-1;
        }
    }
}
int get(int i,int j){

    if(i==0||j==0) cout<<"error?"<<endl;
    if(dp[i][j]!=-1){return dp[i][j];}
    if(i==j) return dp[i][j]=0;
    if(at(i)==at(j)) return dp[i][j]=get(i+1,j-1);
    int second,first;
    second = std::min(get(i,j-1)+del[at(j)-'a'], get(i,j-1)+add[at(j)-'a']);
    first = std::min(get(i+1,j)+del[at(i)-'a'], get(i+1,j)+add[at(i)-'a']);
    return dp[i][j]=std::min(first,second);
}

int main(){

    Init();
    freopen("D://in.txt","r",stdin);
    scanf("%d%d",&m,&n);
    scanf("%s",s);

    char c;
    int tmpa,tmpb;
    for(int i=0;i<m;i++){
        getchar();
        scanf("%c",&c);
        scanf("%d%d",&tmpa,&tmpb);

        add[c-'a']=tmpa;
        del[c-'a']=tmpb;
    }
    cout<<get(1,n)<<endl;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator