SDUTOJ-1650-dp

发布时间:2016-12-9 19:53:42 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"SDUTOJ-1650-dp",主要涉及到SDUTOJ-1650-dp方面的内容,对于SDUTOJ-1650-dp感兴趣的同学可以参考一下。

纯动归问题。 dp[i][j]:前i个字母共用了j个按键,最小的按键次数。 dp[i][j]=min(dp[k][j-1])(k<i); #include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> #include<vector> #define LL long long #define INF 1000000000 using namespace std; vector<int>vec[1001]; char str[10001]; int n,m; int a[10001]; char key[10001]; char let[10001]; int dp[101][101]; int vis[1001]; int nums[101][101]; void dos() { memset(vis,0,sizeof(vis)); int num=0; int i,j,k,z; for(i=0; i<101; i++) { for(j=0; j<101; j++)dp[i][j]=INF; } for(i=1; i<=m; i++) { num+=a[i]*i; dp[1][i]=num; } for(i=1;i<=m;i++) { for(j=1;j<=i;j++) { int num=0; for(k=j;k<=i;k++) { num+=a[k]*(k-j+1); } nums[j][i]=num; } } for(j=2; j<=n; j++) { for(k=j; k<=m; k++) { for(i=1; i<k; i++) { int num=nums[i+1][k]; dp[j][k]=min(dp[j][k],dp[j-1][i]+num); } } } int ipos=m; for(j=n-1; j>=1; j--) { for(i=1; i<ipos; i++) { int num=nums[i+1][ipos]; if(dp[j+1][ipos]==dp[j][i]+num) { vis[i]=1; ipos=i; break; } } } int st=0; printf("%c: ",key[st]); for(i=1;i<=m;i++) { printf("%c",let[i-1]); if(vis[i]) { cout<<endl; st++; printf("%c: ",key[st]); } } cout<<endl; cout<<endl; } int main() { int _,i,j; scanf("%d",&_); for(j=1;j<=_;j++) { scanf("%d%d",&n,&m); scanf("%s",key); scanf("%s",let); for(i=1; i<=m; i++)scanf("%d",&a[i]); printf("Keypad #%d:\n",j); dos(); } return 0; }

上一篇:(译)Objective-C的动态特性
下一篇:尽人事,听天命

相关文章

关键词: SDUTOJ-1650-dp

相关评论