Counting Towers

Main idea of the title:

Build a n × 2 n \times 2 n × The rectangle of 2 can only be constructed with a rectangle. Ask how many different options there are.

Solution:

The division status is whether the last line is connected. f [ i ] [ 0 ] f[i][0] f[i][0] indicates the number of schemes in which the last line is I and the last line is not connected, f [ i ] [ 1 ] f[i][1] f[i][1] indicates the number of schemes in which the last line is I and the last line is connected

                      _  _    _  _    _  _    _  _     _ _
         _  _        | || |  |_|| |  | ||_|  |_||_|   |_ _|
f[i][0]  | || | =>   | || |, | || |, | || |, | || |,  | | |
                       _ _    _ _    _ _ 
          _ _         |   |  |_|_|  |_ _|
f[i][1]   |   |  =>   |   |, |   |, |   |

int n;
ll f[1000005][2];
int main()
{
    int t;
    cin>>t;
    f[1][0]=1,f[1][1]=1;
    for(int i=2;i<=1000000;i++){
        f[i][0]=((f[i-1][0]*4)%mod+f[i-1][1])%mod;
        f[i][1]=((f[i-1][1]*2)%mod+f[i-1][0])%mod;
    }
    while(t--){
        cin>>n;
        cout<<(f[n][0]+f[n][1])%mod<<endl;
    }
    return 0;
}

Projects

Main idea of the title:

There are n projects, and each project has a start time, end time and revenue. You can only participate in one project at a time. Ask what the biggest benefit is.

Solution:

Sort by end time first. Then f[i] represents the maximum benefit of the i-th project. Then the answer is f[n]

Transfer: for the ith project, if not, f[i]=f[i-1] If you do, it is f[i]=f[j] The end time of the j-th project is just less than the start time of the i-th project. Because it was sorted according to the end time, you can find J in two here. therefore f [ i ] = m a x ( f [ i − 1 ] , f [ j ] ) f[i]=max(f[i-1],f[j]) f[i]=max(f[i−1],f[j]).

int n;
struct {
    int a,b,c;
}A[N];
ll f[N];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>A[i].a>>A[i].b>>A[i].c;
    sort(A+1,A+1+n,[](const auto&aa,const auto&bb){
        return aa.b<bb.b;
    });
    f[0]=0;
    A[0].b=-INF;
    for(int i=1;i<=n;i++){
        f[i]=f[i-1];
        int l=0,r=i-1;
        while(l<r){
            int m=l+r+1>>1;
            if(A[m].b<A[i].a) l=m;
            else r=m-1;
        }
        f[i]=max(f[i],f[l]+A[i].c);
    }
    cout<<f[n];
    return 0;
}

Elevator Rides

Main idea of the title:

n groups to be grouped. The sum of each group shall not exceed x. ask how many groups to be divided into at least.

Solution:

Look at the data range and think about the method. N < = 20, think about state compression. I indicates a binary state, 1 indicates that the person has been assigned, and 0 indicates that he has not been assigned. f[i] is the smallest group in the I state. The answer is f [(1 < < n) - 1]

Transfer: if you directly enumerate subsets, the complexity is O ( n ⋅ 3 n ) O(n\cdot 3^n ) O(n ⋅ 3n), and 3 20 = 3 , 486 , 784 , 401 3^{20}=3,486,784,401 320=3,486,784,401. Therefore, subsets cannot be enumerated.

In addition, a state g[i] is used to represent the maximum space left in the allocated group in state I. Then, if a [i] > g[i], you need to open another group.

int n,x;
int A[22];
int f[1<<20],g[1<<20];
int main()
{
    cin>>n>>x;
    for(int i=0;i<n;i++) cin>>A[i];
    memset(f,INF,sizeof f);
    f[0]=1,g[0]=x;
    for(int i=1;i<1<<n;i++){
        for(int j=0;j<n;j++){
            if(!(i>>j&1)) continue;
            if(g[i-(1<<j)]>=A[j]) {
                if(f[i]>f[i-(1<<j)]){
                    f[i]=f[i-(1<<j)];
                    g[i]=g[i-(1<<j)]-A[j]; // g must be transferred when f is transferred, regardless of size
                }else if(f[i]==f[i-(1<<j)]){  // When f is equal, g takes the largest
                    g[i]=max(g[i],g[i-(1<<j)]-A[j]);
                }
            }else {
                if (f[i] > f[i - (1 << j)] + 1) {
                    f[i] = f[i - (1 << j)] + 1;
                    g[i] = x - A[j];
                } else if (f[i] == f[i - (1 << j)] + 1) {
                    g[i] = max(g[i], x - A[j]);
                }
            }
        }
    }
    cout<<f[(1<<n)-1];
    return 0;
}

Counting Numbers

Main idea of the title:

Find all numbers between [a,b], and the number of adjacent numbers is different.

Solution:

Digital dp

dfs(int cur, int lst, int flag) indicates the position of cur, and the number taken in the previous position is the answer of lst.

Note the leading 0. Leading 0 is represented by 10. Therefore, if LST = = 10 & & when 0 is currently taken, the lst passed down is still equal to 10

ll a,b;
int A[20],p;
ll f[20][12];
ll dfs(int cur,int lst,bool flag){
    if(cur<0) return 1;
    if(!flag&&f[cur][lst]!=-1) return f[cur][lst];
    int mx=flag?A[cur]:9;
    ll ret=0;
    for(int i=0;i<=mx;i++){
        if(i==lst) continue;
        if(lst==10&&i==0) // Leading 0
            ret=(ret+dfs(cur-1,10,flag&&i==mx));
        else ret=(ret+dfs(cur-1,i,flag&&i==mx));
    }
    if(!flag) f[cur][lst]=ret;
    return ret;
}
ll solve(ll x){
    p=0;
    memset(f,-1,sizeof f);
    while(x){
        A[p]=x%10;
        x/=10;
        p++;
    }
    return dfs(p-1,10,true);
}
int main()
{
    cin>>a>>b;
    cout<<solve(b)-solve(a-1);
    return 0;
}