题目链接：
http://poj.org/problem?id=3898
题目意思：
有两个字符串，模式串和原串。每个字母有一个权值，a为1，b为2,...z为26
模式串中‘ ？’可以被一个字母代替。
‘*’可以被0个或多个字母代替。
问替换后的模式串满足时原串的子串，求权值和最小的那个值。
解题思路：
dp[i][j]表示模式串的第i个字符和原串的第j个字符匹配时，能达到的最小的权值。
当save1[i]==save2[j]时，dp[i][j]=min(dp[i][j],dp[i-1][j-1]+save2[j]-'0');
当save1[i]=='*'时，dp[i][j]=min(dp[i][j],dp[i-1][k]+sum[j]-sum[k])(0<=k<=j);
当save1[i]=='?'时，dp[i][j]=min(dp[i][j],dp[i-1][j-1]+save2[j]-'0');
用lmin[j]保存下表示不超过j的最小的dp[i-1][k]-sum[k] 则lmin[j]=min(lmin[j-1],dp[i-1][j]-sum[j]);
用lmin[j]数组可以把复杂度降很多。以后要多加留意呵呵。
代码：
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
using namespace std; /*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*/
int dp[1100][11000];
int sum[11000],lmin[11000];
char save1[1100],save2[11000]; int main()
{
while(scanf("%s%s",save1+1,save2+1)!=EOF)
{
int le1=strlen(save1+1),le2=strlen(save2+1); //printf("%d %d\n",le1,le2);
sum[0]=0;
for(int i=1;i<=le2;i++) //sum[i]表示前i个，权值之和
sum[i]=save2[i]-'a'+1+sum[i-1];
for(int i=0;i<=le1;i++) //初始化为最大
for(int j=0;j<=le2;j++)
dp[i][j]=INF;
dp[0][0]=0;
lmin[0]=INF; //用lmin[j]保存下表示不超过j的最小的dp[i-1][k]-sum[k]
//则lmin[j]=min(lmin[j-1],dp[i-1][j]-sum[j])
for(int i=1;i<=le2;i++)
{
dp[0][i]=0;
lmin[i]=min(lmin[i-1],dp[0][i]-sum[i]);
}
bool flag=false;
for(int i=1;i<=le1;i++)
{
lmin[0]=INF;
flag=false;
if(dp[i-1][0]==0) //说明前面有‘*’号的情况
{
if(save1[i]=='*')
{
dp[i][0]=0;
flag=true; //注意这个不能掉
}
}
for(int j=1;j<=le2;j++)
{
if(save1[i]=='?') //当为？号时，可以用任意字母代替
{
if(dp[i-1][j-1]+save2[j]-'a'+1<dp[i][j])
{
flag=true;
dp[i][j]=dp[i-1][j-1]+save2[j]-'a'+1;
}
}
else if(save1[i]=='*') //当为‘*’时，找到lmin[j]，用它来更新
{
if(lmin[j]+sum[j]<dp[i][j])
{
flag=true;
dp[i][j]=lmin[j]+sum[j];
}
}
else if(save1[i]==save2[j]) //直接更新过来
{
if(dp[i-1][j-1]+save2[j]-'a'+1<dp[i][j])
{
dp[i][j]=dp[i-1][j-1]+save2[j]-'a'+1;
flag=true;
}
}
lmin[j]=min(lmin[j-1],dp[i][j]-sum[j]);
//printf("i:%d j:%d %d ",i,j,dp[i][j]);
}
if(!flag) //减一下枝
break;
//putchar('\n');
}
int ans=INF;
for(int j=1;j<=le2;j++)
ans=min(ans,dp[le1][j]);
if(ans==INF)
puts("-1");
else
printf("%d\n",ans);
} return 0;
}