我想每天都写一篇Blog..

贵在坚持...

好了说正文

链接:http://codeforces.com/gym/100212/attachments/download/1727/20042005-winter-petrozavodsk-camp-andrew-stankevich-contest-10-en.pdf

题目大意:

求一串字符串b,使得对于给定的a数组和t数组,满足:

|a(1)-t(b[0],b[1])|+|a(2)-t(b[1],b[2])|+...+|a(n-1)-t(b[n+1]-b[n])|

最小

大致思路:dp

dp[i][j]表示前i个字符,最后一个是j所需要的最小代价

代码如下:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int dp[105][35];
int a[105];
int x[35][35];
int last[105][35];
void dfs(int x,int y)
{
    if (x==0)
    {
        printf("%c",'a'+y);
        return;
    }
    dfs(x-1,last[x][y]);
    printf("%c",'a'+y);
}
int main()
{
    freopen("ssh.in","r",stdin);
    freopen("ssh.out","w",stdout);
    int n,m;
    scanf("%d%d",&n,&m);
    int i;
    for (i=1;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    for (i=0;i<=100;i++)
    {
        int j;
        for (j=0;j<=30;j++)
        {
            dp[i][j]=999999999;
        }
    }
    for (i=0;i<m;i++)
    {
        int j;
        for (j=0;j<m;j++)
        {
            scanf("%d",&x[i][j]);
        }
    }
    for (i=0;i<m;i++)
    {
        dp[0][i]=0;
    }
    for (i=1;i<n;i++)
    {
        int j;
        for (j=0;j<m;j++)
        {
            int k;
            for (k=0;k<m;k++)
            {
                if (dp[i][j]>dp[i-1][k]+abs(a[i]-x[k][j]))
                {
                    dp[i][j]=dp[i-1][k]+abs(a[i]-x[k][j]);
                    last[i][j]=k;
                }
            }
        }
    }
    int min_ans=0;
    for (i=0;i<m;i++)
    {
        if (dp[n-1][min_ans]>dp[n-1][i])
        {
            min_ans=i;
        }
    }
    dfs(n-1,min_ans);
    printf("\n");
    return 0;
}