100212 G 解题报告
我想每天都写一篇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所需要的最小代价
代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 | #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;} |
评论 (0)