《DP练习》

https://ac.nowcoder.com/acm/problem/21302：

注意到x % 3 = (x * 10) % 3.

因为(x * 10) % 3 = (x % 3) * (10 % 3) = x % 3 * 1 = x % 3.

所以对余数dp即可。

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> pii;
const int N = 3e3 + 5;
const int M = 1e4 + 5;
const double eps = 1e-10;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e18
#define dbg(ax) cout << "now this num is " << ax << endl;
inline long long ADD(long long x,long long y) {return (x + y) % Mod;}
inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;}
inline long long MUL(long long x,long long y) {return x * y % Mod;}

string s;
LL dp[51][5];//dp[i][j] - 到第i个，余数为j
void solve() { 
    cin >> s;
    int n = s.size();
    for(int i = 1;i <= n;++i) {
        int x = s[i - 1] - '0';
        for(int j = 0;j < 3;++j) {
            dp[i][j] = ADD(dp[i][j],dp[i - 1][j]);
            dp[i][(j + x) % 3] = ADD(dp[i][(j + x) % 3],dp[i - 1][j]);
        }
        dp[i][x % 3] = ADD(dp[i][x % 3],1);
    }
    printf("%lld
",dp[n][0]);
}   
int main() {
    solve();
  //  system("pause");
    return 0;
}

 https://ac.nowcoder.com/acm/problem/21303:

这题有点无语，题目说可以删()，我以为只能删连续的()，但是其实它是可以隔开的一对一对删。

也就是合法的匹配都可以删，那dp转移的时候利用括号匹配来判断一段能不能删去。

(PS:题解很多都是假的做法.

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> pii;
const int N = 3e3 + 5;
const int M = 1e4 + 5;
const double eps = 1e-10;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e18
#define dbg(ax) cout << "now this num is " << ax << endl;
inline long long ADD(long long x,long long y) {return (x + y) % Mod;}
inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;}
inline long long MUL(long long x,long long y) {return x * y % Mod;}

bool dp[105][105];//dp[i][j] - i,j完全匹配
string a,b;
bool check(int L,int r) {
    if((r - L + 1) % 2 != 0) return false;
    int cnt = 0;
    for(int i = L;i <= r;++i) {
        if(a[i - 1] == '(') cnt++;
        else {
            if(cnt == 0) return false;
            cnt--; 
        }
    }
    return cnt == 0;
}
void solve() { 
    cin >> a >> b;
    int n = a.size(),m = b.size();
    dp[0][0] = 1;
    for(int j = 1;j <= m;++j) {
        for(int i = 1;i <= n;++i) {
            if(a[i - 1] == b[j - 1]) {
                for(int k = 0;k < i;++k) {
                    if(dp[k][j - 1] && check(k + 1,i - 1)) dp[i][j] = 1;
                }
            }
        }
    }
    bool f = 0;
    for(int i = 1;i <= n;++i) {
        if(dp[i][m] && (check(i + 1,n) || i == n)) f = 1;
    }
    printf("%s
",f ? "Possible" : "Impossible");
}   
int main() {
    solve();
    system("pause");
    return 0;
}
/*
(())()
()

()(())
(())
*/