反恐训练营

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 3040    Accepted Submission(s): 693

3

abc

1 1 1

abc

ccc

3

abc

1 1 1

ccc

aba

1

0

还是求最长公共子序列。可是每次遇到同样的字母后。该加上字母相应的分数

#include<stdio.h>

#include<map>

#include<string>

#include<vector>

#include<iostream>

using namespace std;

int N;

int main(int argc, char *argv[])

{

    vector<vector<int> >c;

    map<int,char>m;

    string s,a,b;

    int score;

    while(~scanf("%d",&N))

    {

        cin>>s;

        for(int i=0;i!=s.size();++i)

        {

            scanf("%d",&score);

            m[s[i]]=score;

        }

        cin>>a;

        cin>>b;

        int x=a.size();

        int y=b.size();

        int SIZE=x>y?x:y;

        SIZE+=1;

        c.resize(SIZE);

        for(int i=0;i<c.size();++i)

        {

            c[i].resize(SIZE);

        }

        for(int i=0;i<x;++i)

            c[i][0]=0;

        for(int j=0;j<y;++j)

            c[0][j]=0;

        for(int i=1;i<=x;++i)

            for(int j=1;j<=y;++j)

            {

                if(a[i-1]==b[j-1])

                {

                    c[i][j]=c[i-1][j-1]+m[a[i-1]];

                }

                else if(c[i][j-1]>=c[i-1][j])

                {

                    c[i][j]=c[i][j-1];

                }

                else

                    c[i][j]=c[i-1][j];

            }

        printf("%d\n",c[x][y]);

    }

    return 0;

}