luogu 动态规划口胡合集

P1831 杠杆数

是否说出正解： ×

显然是个数位DP，但是感觉无从下手，事实上可以做18次数位dp，每次枚举支点，就可以算出每个数的力矩，取出力矩为0的作为贡献即可

#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x)
#define Pri(x) printf("%d\n", x)
#define Prl(x) printf("%lld\n",x)
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second 
typedef vector<int> VI;
LL read(){LL x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();}
while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
const double PI = acos(-1.0);
const double eps = 1e-9;
const int maxn = 110;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int N,M,K,now;
int str[20];
LL dp[20][3000];
LL dfs(int pos,int val,int limit){
    if(!pos) return val == 0;
    if(val < 0) return 0;
    if(!limit && ~dp[pos][val]) return dp[pos][val];
    LL ans = 0;
    int up = limit?str[pos]:9;
    for(int i = 0 ; i <= up; i ++){
        ans += dfs(pos - 1,val + i * (pos - now),limit && (i == up));
    }
    if(!limit) dp[pos][val] = ans;
    return ans;
}
LL solve(LL x){
    if(!x) return 1;
    int l = 0;
    LL m = x;
    while(m){
        l++; str[l] = m % 10;
        m /= 10;
    }
    LL ans = 0;
    for(int i = 1; i <= l; i ++){
        Mem(dp,-1);
        now = i;
        ans += dfs(l,0,1);
    }
    return ans - (l - 1);
}
int main(){
    LL l = read(),r = read();
    Prl(solve(r) - solve(l - 1));
    return 0;
}

View Code

P2939 [USACO09FEB]改造路Revamping Trails

是否说出正解：√

很原题了 最短路维护dis[i][j]表示到i点已经经过了j条高速公路的最短路， Dijkstra直接维护即可

P2198 杀蚂蚁

是否说出正解：√

似乎dp[x][y]表示经过了x个放射塔，y个放射塔的最小值即可，干扰塔数量用n - x - y表示

dp[x][y] = min(dp[x - 1][y] + (x - 1) * g * (t + y * b),dp[x][y - 1] + x * g  * (t + (y - 1) * b,dp[x][y] + (x + r) * g * (t + y * b) 

P4766 [CERC2014]Outer space invaders

是否说出正解： ×

离散化之后区间dp

#include<bits/stdc++.h>
using namespace std;
const int maxn = 6010;
const int INF = 0x3f3f3f3f;
int N;
struct Node{
    int l,r,d;
    Node(int l = 0,int r = 0,int d = 0):l(l),r(r),d(d){}
}node[maxn];
int Hash[maxn];
int dp[maxn][maxn];
int main(){
    int T; scanf("%d",&T);
    while(T--){
        scanf("%d",&N); int cnt = 0;
        for(int i = 1; i <= N; i ++){
            scanf("%d%d%d",&node[i].l,&node[i].r,&node[i].d);
            Hash[++cnt] = node[i].l; Hash[++cnt] = node[i].r;
        }
        sort(Hash + 1,Hash + 1 + cnt);
        cnt = unique(Hash + 1,Hash + 1 + cnt) - Hash - 1;
        for(int i = 1; i <= N ; i ++){
            node[i].l = lower_bound(Hash + 1,Hash + 1 + cnt,node[i].l) - Hash;
            node[i].r = lower_bound(Hash + 1,Hash + 1 + cnt,node[i].r) - Hash;
        }
        for(int len = 1; len <= cnt; len ++){
            for(int l = 1; l + len - 1 <= cnt; l ++){
                int r = l + len - 1;
                int id = 0;
                for(int i = 1; i <= N ; i ++){
                    if(node[i].l < l || node[i].r > r) continue;
                    if(!id || node[id].d < node[i].d) id = i;
                }
                if(!id){
                    dp[l][r] = 0;
                    continue;
                }
                dp[l][r] = INF;
                for(int k = node[id].l; k <= node[id].r; k ++){
                    dp[l][r] = min(dp[l][r],dp[l][k - 1] +dp[k + 1][r] + node[id].d);
                }
            }
        }
        printf("%d\n",dp[1][cnt]);
    }
    return 0;
}

View Code