Software Industry Revolution Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 263 Accepted: 86 Description Making revolutions in the software industry is not an easy task. That’s why this problem is about something else. Stanescu has just invented a new super-cool way to develop software. It is similar to writing program code, but instead of writing it, you ask some else to do it. In such way, one could create great software, without even knowing what a Turing Machine is. As you can see, this is not just software industry revolution. Really, Stanescu does not care about the software industry at all. He just wants to make money. In order to protect the money he is going to make, he needs to pick a special password for his bank account, satisfying the following requirements: The password should not be too complex, so that Stanescu can remember it. The complexity of a password is the sum of the complexity of its characters and the complexity of a character is its position in the alphabet (for ’a’ it is 1, for ’b’ – 2, and so on). For example, the complexity of the string ”ala” is 1 + 12 + 1 = 14; It should match a given pattern string (composed of lowercase Latin letters, ’?’ and ’*’, no longer than 1000 characters). ’?’ is matched by one arbitrary lowercase Latin letter, and ’*’ – by zero or more arbitrary lowercase Latin letters; It should be a sub-string of given super-password string (composed of lowercase Latin letters, no longer than 10000). You have to write a program that computes the complexity of simplest possible password. Input Several test cases are given at the input. Each of them consists of a single line containing the pattern and the super-password strings separated by a white space. Output For each test case, your program should print a single line with one integer – the complexity of the simplest possible password. If no password satisfies the given requirements, the program should print -1. Sample Input a?a alabala a*c?a axcbaabcbaxSample Output 4 9Hint Explanation: Test case #1: aba is the simplest password Test case #2: abcba is simpler than axcba 這題考的是dp，可是我們一般很難寫出狀態轉移方程，看解題報告還要看半天才知道什麼意思，這個題我幾乎就是copy解題報告的啊，雖然都是自己手打的，哎。。。。就當是解說員吧
/*
dp[i][j]代表模式串的第i個和原串的第j個匹配的時候最小值。
對於?
dp[i][j]=dp[i-1][j-1]+cost[j,j]
對於字母，要求mat[i]==pat[j]才能轉移。
dp[i][j]=dp[i-1][j-1]+cost[j,j]
sum[i]代表原串前i個代價的總和
對於*
dp[i][j]=min{dp[i-1][k]+cost[k+1,j]} for k>=0&&k<=j
對於這個式子的話看起來要枚舉K，這樣顯然不行。
我們可以轉化
dp[i-1][k]+cost[k+1,j]
=dp[i-1][k]+sum[j]-sum[k]=(dp[i-1][k]-sum[k])+sum[j]
(dp[i-1][k]-sum[k])這個是一個只和k有關的式子。
我們可以保存一個(dp[i-1][k]-sum[k])最小值。這樣就可以o(1)得到dp[i][j]了。
*/
#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
char str[1050],pass[10050];
int sum[10050],record[27],dp[1005][10050];
int main ()
{
int i,j,cur,n,m;
bool flag;
while(scanf("%s%s",str+1,pass+1)!=EOF)
{
n=strlen(str+1);
m=strlen(pass+1);
sum[0]=0;
for(i=0;i<26;i++)
record[i]=0;
for(i=1;i<=m;i++)
{
record[pass[i]-'a']++;
}
for(i=1;i<=n;i++)
{
if(str[i]>='a')//沒想到問題出在這，數組越界了oj盡然沒提示RE卻提示WA
record[str[i]-'a']--;
}
for(i=0;i<26;i++)
{
if(record[i]<0)
break;
}
if(i<26)//這是最開始的優化，明顯不合題意的去掉
{
printf("-1\n");
continue;
}
for(i=1;i<=m;i++)
{
sum[i]=pass[i]-'a'+1+sum[i-1];
}
for(i=0;i<=n;i++)
for(j=0;j<=m;j++)
dp[i][j]=10000000;
for(i=0;i<=m;i++)//str[1]得特殊操作，給dp[1][j]一個初始值
{
if(i>0&&(str[1]=='?'||str[1]==pass[i]))//第一位為？或者和pass[i]相等那dp[1][i]當然就是str[1]對應的值也是sum[i]-sum[i-1]
{
dp[1][i]=sum[i]-sum[i-1];
}
else if(str[1]=='*')//*有點特殊，它的取值是不定的，但是這題要求最小的值，如果str第一個為*，那我們完全可以不取任何值，也就是0
{
dp[1][i]=0;
}
}
for(i=2;i<=n;i++)
{
flag=0;
if(str[i]=='*')
{
cur=10000000;
if(dp[i-1][0]==0)
{
flag=1;
dp[i][0]=0;
cur=0;//記錄一下最小值
}
for(j=1;j<=m;j++)
{
if(dp[i-1][j]-sum[j]<cur)
cur=dp[i-1][j]-sum[j];
if(sum[j]+cur<dp[i][j])
{
dp[i][j]=sum[j]+cur;
flag=1;
}
}
}
else
{
for(j=1;j<=m;j++)
{
if(dp[i-1][j-1]==10000000)
continue;//簡化運算
if(str[i]=='?'||str[i]==pass[j])
{
if(dp[i][j]>dp[i-1][j-1]+pass[j]-'a'+1)
{
dp[i][j]=dp[i-1][j-1]+pass[j]-'a'+1;
flag=1;
}
}
}
}
if(!flag)//若flag為0，那就說明上面沒有任何操作，沒有符合條件的情況了，找不到適合的解了
break;
}
if(i<=n)//程序沒有全部執行，str並沒有在pass中全部找到
{
printf("-1\n");
continue;
}
cur=100000000;
for(i=0;i<=m;i++)//應該是從零開始，如果str是*結果就是0
{
if(cur>dp[n][i])//str中的字母都找完了
cur=dp[n][i];
}
if(cur==100000000)
printf("-1\n");
else
printf("%d\n",cur);
}
return 0;
}
