递推,动态规划(DP),字符串处理,最佳加法表达式

看了一些资料,竟然发现连百度文库也有错误的地方,在这里吐槽一下
题目大意:http://wenku.baidu.com/link?url=DrUNNm19IqpPNZjKPX4Jg6shJiK_Nho6dPf8I0b5unSmQM6Ji7tNTKU1LFWDyiCoJaMj8hHb_AakLqFZFuz0vxwWHiSdTLqn10FsO2tZx6W
上面还有我的评论哦。

解题报告:
1、对于每一节字符串表示的数,用二维数组sum[i][j]记录
2、状态转移方程
f[i][j]=min(f[i-k][j-1]+num[i-k+1][j]);
3、也是吐槽百度文库的地方,一定记得-'0';

#include <stdio.h>
#include <string.h>
#define MAX 105
#define INF 0x3f3f3f3f void DP(char *a,int t,int m)//t为加号个数,m为字符串长度
{
int i,j,d,k,min;
int f[m+][t+];//f[i][j]表示在前i个字符中插入j个加号所能达到的最小值;
int num[m+][m+];//二维数组来存每一节数字的大小,num[i][j]表示字符串从i到j的大小;
for(i=; i<=m; i++)
{
for(j=,d=; j<=m; j++)
{
if(i>j)//不能构成数字
num[i][j]=INF;
else
{
d=d*+a[j]-'';
num[i][j]=d;
}
}
}
//状态转移方程
//f[m][j]=min(f[m-i][j-1]+num[m-i+1][m]),这里枚举i的位置
for(i=; i<=m; i++)
{
for(j=; j<=t; j++)
{
if(j>=i)
f[i][j]=INF;
else if(j==)
f[i][j]=num[][i-];
else
{
for(min=INF,k=; k<i; k++) //开始枚举i的位置
{
f[i][j]=f[i-k][j-]+num[i-k][i-];
if(min>f[i][j])
min=f[i][j];
}
f[i][j]=min;//存起来
}
}
}
printf("%d\n",f[m][t]);
} int main()
{
int times;
int len;
char arr[MAX];
scanf("%s",arr);
scanf("%d",&times);
len=strlen(arr);
DP(arr,times,len);
return ;
}
上一篇:判断IE版本的HTML语句详解 - AnswerCard


下一篇:JavaScript 注释