SRM468

250pt

给定手机0-9按键对应的英文字母（1个对多个），0固定对应空格。然后在给定一些单词。以及一个要处理的串，叫你按照那个串模拟输出结果

思路：

大模拟，写的有点乱

 // BEGIN CUT HERE

 /*

 */

 // END CUT HERE

 #line 7 "T9.cpp"

 #include <cstdlib>

 #include <cctype>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 #include <algorithm>

 #include <vector>

 #include <string>

 #include <iostream>

 #include <sstream>

 #include <map>

 #include <set>

 #include <queue>

 #include <stack>

 #include <fstream>

 #include <numeric>

 #include <iomanip>

 #include <bitset>

 #include <list>

 #include <stdexcept>

 #include <functional>

 #include <utility>

 #include <ctime>

 using namespace std;

 #define PB push_back

 #define MP make_pair

 #define REP(i,n) for(i=0;i<(n);++i)

 #define FOR(i,l,h) for(i=(l);i<=(h);++i)

 #define FORD(i,h,l) for(i=(h);i>=(l);--i)

 typedef vector<int> VI;

 typedef vector<string> VS;

 typedef vector<double> VD;

 typedef long long LL;

 typedef pair<int,int> PII;

 struct oo{

      string d, s;

      bool operator <(const oo &b)const{

           if (s < b.s || (s == b.s && d < b.d)) return true;

           return false;

      }

 };

 class T9

 {

         public:

         char d[];

         oo S[];

         int n, m, k;

         string find(string a, int k){

               int cnt = ;

               for (int i = ; i < m; ++i){

                    if (S[i].s == a) ++cnt;

                    if (cnt == k) return S[i].d;

               }

               return "";

         }

         string message(vector <string> part, vector <string> dict, vector <string> keystr)

         {

                 n = part.size(), m = dict.size(), k = keystr.size();

                 for (int i = ; i < n; ++i)

                     for (int j = ; j < part[i].size(); ++j)

                        d[(int)part[i][j]] = i + ;

                 for (int i = ;  i < m; ++i){

                     S[i].d = dict[i];

                     S[i].s.clear();

                     for (int j = ; j < dict[i].size(); ++j)

                         S[i].s.push_back(d[dict[i][j]]);

                 }

                 sort(S, S + m);

                 string ans = "";

                 int cnt = ;

                 string tmp = "";

                 string ks = accumulate(keystr.begin(), keystr.end(), string(""));

                 int k = ks.size();

                 for (int i = ; i < k; ++i){

                     if (ks[i] == '*'){ cnt += ; continue; }

                     if (ks[i] == '#'){ cnt += ; continue; }

                     if ((ks[i] < '' || ks[i] > '') && (int)tmp.size() > ){

                            ans += find(tmp, cnt + );

                            cnt = ;

                            tmp.clear();

                     }

                     if (ks[i] == '') ans += ' ';

                     if (ks[i] > '' && ks[i] <= '') tmp += ks[i];

                 }

                 if ((int)tmp.size() > ) ans += find(tmp, cnt + );

                 return ans;

         }

 };

500pt

给定n（n <= 40w）个城市，然后在给定2个数组(需要按照给定的算出来)，一个为不坐飞机情况下i->i+1所用的时间，一个为作为飞机所用的时间

求在不超过坐k次飞机的情况下，最少时间（一次可以连续做多个城市，但必须连续，比如i->i+1->i+2..）

思路：

动态规划

dp[i][j][k]表示当前到i城市，做了j次飞机，k（0或1）表示最后一次做没做飞机所用的最少时间

方程应该很好推。但要用滚动数组

 // BEGIN CUT HERE

 /*

 */

 // END CUT HERE

 #line 7 "RoadOrFlightHard.cpp"

 #include <cstdlib>

 #include <cctype>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 #include <algorithm>

 #include <vector>

 #include <string>

 #include <iostream>

 #include <sstream>

 #include <map>

 #include <set>

 #include <queue>

 #include <stack>

 #include <fstream>

 #include <numeric>

 #include <iomanip>

 #include <bitset>

 #include <list>

 #include <stdexcept>

 #include <functional>

 #include <utility>

 #include <ctime>

 using namespace std;

 #define PB push_back

 #define MP make_pair

 #define REP(i,n) for(i=0;i<(n);++i)

 #define FOR(i,l,h) for(i=(l);i<=(h);++i)

 #define FORD(i,h,l) for(i=(h);i>=(l);--i)

 #define Inf (1LL << 50)

 typedef vector<int> VI;

 typedef vector<string> VS;

 typedef vector<double> VD;

 typedef long long LL;

 typedef pair<int,int> PII;

 long long rT[], fT[];

 long long dp[][][];

 class RoadOrFlightHard

 {

         public:

         long long minTime(int N, int roadFirst, int roadProd, int roadAdd, int roadMod, int flightFirst, int flightProd, int flightAdd, int flightMod, int K)

         {

                rT[] = roadFirst % roadMod;

                fT[] = flightFirst %  flightMod;

               // cout << rT[0] << endl;

                for (int i = ; i < N; ++i){

                      rT[i] = (rT[i-]*roadProd + roadAdd) % roadMod;

                      fT[i] = (fT[i-]*flightProd + flightAdd) % flightMod;

                }

                for (int i = ; i <= K; ++i)

                     dp[][i][] = dp[][i][] = Inf;

                dp[][][] = ;

                for (int i = ; i < N; ++i){

                     int cur = i & ;

                     for (int j = ; j <= K; ++j)

                         dp[cur^][j][] = dp[cur^][j][] = Inf;

                     for (int j = ; j <= K; ++j){

                         if (dp[cur][j][] < Inf){

                              if(j < K) dp[cur^][j+][] = min(dp[cur^][j+][], dp[cur][j][] + fT[i]);

                              dp[cur^][j][] = min(dp[cur^][j][], dp[cur][j][] + rT[i]);

                         }

                         if (dp[cur][j][] < Inf){

                              if(j < K) dp[cur^][j+][] = min(dp[cur^][j+][], dp[cur][j][] + fT[i]);

                              dp[cur^][j][] = min(dp[cur^][j][], dp[cur][j][] + fT[i]);

                              dp[cur^][j][] = min(dp[cur^][j][], dp[cur][j][] + rT[i]);

                         }

                     }

                }

                long long ans = Inf;

                for (int i = ; i <= K; ++i)

                   for (int j = ; j <= ; ++j)

                       ans = min(ans, dp[N & ][i][j]);

                return ans;

         }

 };