4-16补题 第3次训练

F Space Elevator

牛想上太空，没话说。用k种积木来搭建一个梯子。每种积木都有三个参数：数量c，高度h，这种积木最大能到达的高度a，即这种积木不能搭在a以上的地方。
数据量较小，01背包和多重背包都可，先把这些积木按照最大高度a从小到大排序，然后再求解问题。
还要注意一点，再最终输出答案时，因为所有积木的a不同，答案可能不在dp[max_a]里，要遍历一次dp寻找答案。dp[i]表示高度小于i时梯子的最大高度。

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
typedef struct block{
    int h,a;
}block;
block tmp;
vector<block> v;
int dp[40500];
bool cmp(block a,block b){
    return a.a < b.a;
}
int main(){
    int k,tot=0;
    int a,c,h;
    scanf ("%d",&k);
    v.reserve(4000);
    for (int i=1;i<=k;i++){
        scanf ("%d %d %d",&h,&tmp.a,&c);
        int j=1;
        for (j=1;2*j-1<=c;j<<=1){
            tmp.h = h*j;
            v.push_back(tmp);
        }
        if (j-1<c){
            tmp.h = h * (c-j+1);
            v.push_back(tmp);
        }
    }
    sort(v.begin(),v.end(),cmp);
    tot = v.size();
    for (int i=0;i<tot;i++){
        for (int j=v[i].a;j>=v[i].h;j--){
            dp[j] = max(dp[j],dp[j-v[i].h]+v[i].h);
        }
    }
    int ans = 0;
    for (int i=0;i<=v[tot-1].a;i++) ans = max(ans,dp[i]);
    printf ("%d\n",ans);
    return 0;
}

J Two strings

字符串匹配+dp，输入两个字符串是s1,s2，问s2是否可以匹配出s1.
'.'可以匹配任意一个字符，'*'可以将前面的字符复制任意次。
s1中的字符被匹配的情况有以下几种：
1.被相同的字符匹配
2.被'.'匹配
3.被'*'复制匹配
因为在leetcode中碰到过相似的题目，在leetcode中<"abc","a.*">是可以匹配成功的，在这道题中却不行，导致wa了n次。还要注意这道题中*可能吞噬它前面的那个字符(复制0次)。

#include <algorithm>
#include <cstring>
#include <vector>
#include <iostream>
using namespace std;
const int maxn = 2505; 
int len1,len2;
bool dp[maxn][maxn];
char s1[maxn],s2[maxn];
int main(){
    std::ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--){
        cin >> s1+1 >> s2+1;
        memset (dp,0,sizeof dp);
        len1 = strlen(s1+1),len2 = strlen(s2+1);
        dp[0][0] = 1;
        int x = 0;
        while (s2[x+2]=='*')    dp[0][x] = 1,x += 2;
        for (int i=1;i<=len1;i++){
            for (int j=1;j<=len2;j++){
                if (s1[i]==s2[j] || s2[j]=='.') dp[i][j] = dp[i-1][j-1];
                if (s2[j]=='*'){
                    if (dp[i][j-2] || dp[i][j-1] || (s1[i-1]==s1[i] && dp[i-1][j]))
                        dp[i][j] = 1;
                }
            }
        }
        cout << (dp[len1][len2]?"yes":"no") << endl;
    }
    return 0;
}