UVALive – 7544 Banking II 朴素dp、类似于背包的dp

7544 Banking II 朴素dp、类似于背包的dp

Source

UVALive - 7544

My Solution

题意：给出一个数字字符串，然后给出一个由小写字母构成的字符串，每个小写字母x 表示 有且必须选择一段连续的长度为 x - 'a' + 1的数字字符，然后要求这些小写字母按顺序选取数字字符串的子串，求选取的数字的和的最大值

朴素dp、类似于背包的dp

定义dpij 表示当前在考略第i个小写字母，将要选取的数字字符串子串是 [j - ( k[i] - 'a' + 1), j]，时已经选中的数字的和的最大值，

每次初始为 dpij = dpi-1j，然后进行转移即可

复杂度 O(n^2)

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 256 + 8;

int dp[maxn][maxn], sum[maxn];
string s1, s2;
int main()
{
    #ifdef LOCAL
    freopen("c.txt", "r", stdin);
    //freopen("c.out", "w", stdout);
    int T = 1;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    int sz1, sz2, i, j, ans = 0;
    while(getline(cin, s1)){
        memset(dp, 0, sizeof dp);
        memset(sum, 0, sizeof sum);
        //cin >> s2;
        getline(cin, s2);
        sz1 = s1.size(), sz2 = s2.size();
        //sum[] = s1[0] - '0';
        for(i = 0; i < sz1; i++){
            sum[i + 1] = sum[i] + (s1[i] - '0');
        }
        ans = 0;
        for(i = 0; i < sz2; i++){
            for(j = 1; j <= sz1; j++){ dp[i][j] = dp[i][j-1]; if(i != 0) { if(j - (s2[i] - 'a' + 1) >= 0) dp[i][j] = max(dp[i][j], dp[i-1][j - (s2[i] - 'a' + 1)] + sum[j] - sum[j - (s2[i] - 'a' + 1)]);
            }

                else{if(j - (s2[i] - 'a' + 1) >= 0) dp[i][j] = max(dp[i][j], sum[j] - sum[j - (s2[i] - 'a' + 1)]);}
                ans = max(ans, dp[i][j]);
            }
        }
        cout << ans << "n";
    }



    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx