#include <iostream>
#include <string>
#define SIZE 159
#define MAX 555599999
using namespace std;
struct x
{
    int value;
    string pos;
}f[SIZE][SIZE];
bool used[SIZE][SIZE];

int init_pos,init_id,value[SIZE];
string str_id,str_pos;
int Dis(const int pos_1,const int pos_2)
{
    int result=0,ptr=1;
    for (int i=pos_1;i<=pos_2;i++)
    {
        result+=value[i]*ptr;
        ptr++;
    }
    return result;
}

struct x DP(const int pre_pos, const int pre_id)
{
    if (used[pre_pos][pre_id]) return f[pre_pos][pre_id];

    struct x Min;
    Min.value=MAX;

    Min.pos+=str_pos[pre_pos-1];

    if (pre_id==init_id)
    {
        Min.value=Dis(pre_pos,init_pos);
        return Min;
    }
    string min_str;

    for (int cur_pos=pre_pos+1; cur_pos<=init_pos+1-(init_id-pre_id); cur_pos++)
    {
        struct x cur_min=DP(cur_pos,pre_id+1);
        cur_min.value+=Dis(pre_pos,cur_pos-1);
        if (cur_min.value<Min.value)
        {
            Min.value=cur_min.value;
            min_str=cur_min.pos;
        }
    }
    Min.pos+=min_str;
    //
    f[pre_pos][pre_id]=Min;
    used[pre_pos][pre_id]=true;
    //
    return Min;
}


int main()
{
    int circle;
    scanf ("%d",&circle);
    for (int tmp=1;tmp<=circle;tmp++)
    {
    cin>>init_id>>init_pos;
    cin>>str_id;
    cin>>str_pos;
    for (int i=1;i<=init_pos;i++) cin>>value[i];
    memset(used,false,sizeof(used));

    struct x result=DP(1,1);
    int ptr=0,ptr_2=1;
    printf ("Keypad #%d:\n",tmp);
    for (int i=0;i<init_id;i++)
    {
        printf ("%c: %c",str_id[i],str_pos[ptr++]);

        while (ptr<init_pos&&str_pos[ptr]!=result.pos[ptr_2])
        {
            printf ("%c",str_pos[ptr++]);
        }
        ptr_2++;
        printf ("\n\n");
    }
    //cout<<result.pos+"    "<<result.value<<endl;
    }
    return 0;
}

• Re:TLe了 递推写的 哪里还可以优化吗? (232) L18 2009-06-15 02:28:50
  • Re:哦 谢谢啊 (19) hello1806 2009-06-16 15:28:54