Aizu2130-Billion Million Thousand-dp

 1 #include <cstdio>
 2 #include <string>
 3 #include <algorithm>
 4 #include <iostream>
 5 
 6 using namespace std;
 7 
 8 const int INF = 0x3f3f3f3f;
 9 const int maxn = 2000;
10 
11 int N,v[maxn],len[maxn];
12 int dp[maxn];
13 
14 string s[maxn],str;
15 
16 int main()
17 {
18     int cas = 1;
19     while(cin >> N && N)
20     {
21         for(int i=0;i<N;i++)
22         {
23             cin >> s[i] >> v[i];
24             len[i] = s[i].length();
25         }
26         cin >> str;
27         int length = str.length();
28 
29         for(int i=0;i<=length;i++) dp[i] = -INF;
30         dp[0] = 0;
31 
32         for(int i=0;i<=length;i++)
33         {
34             for(int j=0;j<N;j++)
35             {
36                 int End = i - len[j];
37                 if(End>=0 && dp[End]>=0 && str.substr(End,len[j]) == s[j])
38                     {dp[i] = max(dp[i],dp[End]+v[j]);}
39             }
40         }
41 
42         int mx = dp[length];
43 
44         for(int i=0;i<=mx;i++) dp[i] = INF;
45         dp[0] = 0;
46 
47         for(int i=0;i<N;i++)
48         {
49             for(int j=0;j<=mx-v[i];j++)
50                 dp[j+v[i]] = min(dp[j+v[i]] , dp[j]+len[i]);
51         }
52         cout << "Case "<<cas++<< ": " << dp[mx] << endl;
53     }
54 }