本文共 7666 字，大约阅读时间需要 25 分钟。

EASY

给一个长为n(n<2000)的序列A，将其变成一个非增或非减的序列B的绝对值改变量。

key：B中所有的数都是A中的数。因为若$a_l<b<a_r$时，总能令b变成其中一个值。则枚举$b_i$为每个A中的值即可。dp[i][j]表示$b_i\le un{q}_j$时，目前的最小代价。

// #include
   
    #include
    
     #include
     
      using namespace std;typedef long long ll;const int N = 2e3+4;int n,m;int a[N],unq[N];int dp[N][N];int solve(){
       for(int i=0;i
      
       >n;    for(int i=0;i
       
        >a[i];        unq[i]=a[i];    }    sort(unq,unq+n);    m=unique(unq,unq+n)-unq;    int ans=solve();    reverse(a,a+n);    ans=min(ans,solve());    cout<
        
         <
        
       
      
     
    
   

题意：给出$m$个时间区间，完成每个区间的事可以有一定的贡献。每做完一件事要缓$r$分钟。问最多有多少贡献。

思路：由于时间范围为1e6。我和大部分题解双重循环区间不同。我遍历一遍时间。dp[i]表示前i分钟做的最大贡献。缓r分钟解决方式是每个区间的结束时间$+r$。天坑：一个区间的ending_time可以开始另一件事了。

// #include
   
    #include
    
     #include
     
      #include
      
       using namespace std;typedef long long ll;const int N = 1e6+4,M=1e3+5;struct Node{
       int l,v,nex;}e[M];int n,m,r;ll dp[N+N];unordered_map
       
         head;void add(int a,int b,int c){
       static int cnt=0;    e[++cnt] = Node{
   a,c,head.count(b) ? head[b] : 0};    head[b] = cnt;}int main(){
       cin>>n>>m>>r;    for(int a,b,c,i=1;i<=m;++i){
           cin>>a>>b>>c;        if(b<=n)add(a,b+r,c);    }    for(int i=1;i<=n+r;++i){
           dp[i] = dp[i-1];        if(head.count(i))for(int j=head[i];j;j=e[j].nex){
               dp[i]=max(dp[e[j].l]+e[j].v,dp[i]);        }    }    cout<
        
         <
        
       
      
     
    
   

给一个$n\times n$(n<1000)字符矩阵。求沿对角线丿对称的最大子矩阵。dp[siz][i][j]表示右下角坐标为(i,j)，大小为siz+1的矩阵是否是对称矩阵。

// #include
   
    #include
    
     #include
     
      #include
      
       using namespace std;#define debug(_x) cout<<#_x<<": "<<_x<
       
        >n&&n){
           for(int i=0;i
        
         >a[i]; reverse(a[i],a[i]+n); } for(int i=0;i
        
       
      
     
    
   

题意：给$n(n\le 5000)$个数，选择一个起始点，可以让颜色相同的整段变色。问最少的变色次数，让所有颜色相同。

思路：假设选好了起始点$i$，则如何求变色次数？显然答案是$n-1-f[i-1][i+1]$，其中$f[i-1][i+1]$代表$c_1\cdots c_{i-1}$与$c_n\cdots c_{i+1}$的最长公共子序列。则直接求原数组和逆序数组的最长公共子序列即可。$O(n^2)$

#include
   
    #define IOS ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);using namespace std;const int N = 5005;int f[N][N], c[N];int main(){
       IOS;    int n;    cin >> n;    for(int i = 1; i <= n; ++i){
           cin >> c[i];    }    n = unique(c + 1, c + n + 1) - c - 1;    for(int i = 1; i <= n; ++i){
           for(int j = n; j > 0; --j){
               f[i][j] = max({
   f[i-1][j], f[i][j+1], f[i-1][j+1] + (c[i] == c[j])});        }    }    int ans = 0;    for(int i = 1; i <= n; ++i)        ans = max(ans, f[i-1][i+1]);    cout << n - 1 - ans << endl;}
   

MID

题意：有$n(n\le 100)$个玻璃杯，每个玻璃杯的容量是$a_i$，已有水量是$b_i$，倒水有一半的损失。挑$k$个杯子装水，求最大的装水量。

第一个思路：dp[i][k][j]表示$1...i$个杯子，挑$k$个，剩余容量为j的最大装水量。但是这个状态转移具有后效性，可能前面后面要的杯子，用前面的杯子里的水。 题解：dp[i][k][j]表示$1...i$个杯子，挑$k$个，总容量为$j$的最大水量（未考虑是否装的下，只考虑有多少水）。状态转移如下。则取$k$杯的答案就是max(j, dp[i][k][j])。时间复杂度$O(n^3\cdot \max a)$，达到1e8。

dp[i][k][j]=max(dp[i-1][k][j] + b[i]/2, dp[i-1][k-1][j-a[i]] + b[i]);

#include
   
    #define IOS ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);using namespace std;using ll = long long;const int N = 1e2 + 5;int dp[N][N][10005];int a[N], b[N], ans[N];int main(){
       IOS;    int n, CAP = 0;    cin >> n;    for(int i = 1; i <= n; ++i)        cin >> a[i] >> b[i];    memset(dp, 0xf0, sizeof(dp));    dp[0][0][0] = 0;    for(int i = 1; i <= n; ++i){
           CAP += a[i];        for(int k = 0; k <= n; ++k){
               for(int j = 0; j <= CAP; ++j){
                   int &now = dp[i][k][j];                now = dp[i-1][k][j] + b[i];                if(k && j - a[i] >= 0)now = max(now, dp[i-1][k-1][j-a[i]] + 2 * b[i]);                if(ans[k] < min(now, 2 * j))ans[k] = min(now, 2 * j);            }        }    }    for(int k = 1; k <= n; ++k)        cout << fixed << setprecision(6) << ans[k] / 2.0 << " ";    cout << endl;}
   

题意：给定$n\times m$矩阵，每行选最多$m/2$个。求能被$mod$整除的最大和。（所有数小于70）

思路：对于第$i$行来说，$f[j][h][k]$表示$1...j$取$h$个，对$mod$取余为$k$的最大和。易得转移公式 $$\begin{gathered} f[j][h][k]=\max (f[j-1][h][k], \\ f[j-1][h-1][(mod+k-a[i][j]\%mod)\%mod]+a[i][j]) \end{gathered}$$ 最后，$sum[i][k]={\max }_{j,h}f[j][h][k]$，再对行进行dp $$dp[i][k]=\underset{0\le la<mod}{\max }(,dp[i-1][la]+sum[i][(mod+k-la)$$ 最终答案就是$dp[n][0]$，时间复杂度为$O(n\cdot m^2\cdot mod)$

#include
   
    #define IOS ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);using namespace std;using ll = long long;const int N = 73;int f[N][N/2][N], sum[N][N], dp[N][N];int main(){
       IOS;    int n, m, mod;    cin >> n >> m >> mod;    memset(dp, 0xf0, sizeof(dp));    memset(sum, 0xf0, sizeof(sum));    dp[0][0] = 0;    for(int now, i = 1; i <= n; ++i){
           memset(f[0], 0xf0, sizeof(f[0]));        f[0][0][0] = 0;        sum[i][0] = 0;        for(int j = 1; j <= m; ++j){
               cin >> now;            for(int h = 0; h <= m / 2; ++h){
                   for(int k = 0; k < mod; ++k){
                       f[j][h][k] = f[j-1][h][k];                    if(h && f[j][h][k] < f[j-1][h-1][(mod+k-now%mod) % mod] + now)                        f[j][h][k] = f[j-1][h-1][(mod+k-now%mod) % mod] + now;                    if(sum[i][k] < f[j][h][k])                        sum[i][k] = f[j][h][k];                }            }        }        for(int k = 0; k < mod; ++k){
               for(int la = 0; la < mod; ++la){
                   dp[i][k] = max(dp[i][k], dp[i-1][la] + sum[i][(mod+k-la)%mod]);            }        }    }    cout << dp[n][0] << endl;}
   

题意：给$n(n\le 500)$个数，若相邻两个数相同（$a_i==a_{i+1}$）则可以用$a_i+1$代替。问最后合并出最少的项数。

思路：

• 先考虑只有相邻的多个数合并成一个数的所有情况。当可以合并成一个数时，这个数必然是唯一的。即$num[i][j]$表示把$a_i\cdots a_j$合并成一个数，那个数的值，如果不能的话，$num[i][j]=0$.就是一个简单的区间DP
• 再考虑最少用多少个数即$num$区间来得到整个$1\cdots n$区间。设$f[i]$表示$1\cdots i$区间最少有多少个数。
  $$f[i]=\underset{0\le j<i}{\min }f[j]+1(ifnum[j+1][i]\ne 0)$$

#include
   
    #define IOS ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);using namespace std;using ll = long long;const int N = 505;int num[N][N], f[N];int main(){
       IOS;    int n;    cin >> n;    for(int i = 1; i <= n; ++i)        cin >> num[i][i];    for(int len = 2; len <= n; ++len){
           for(int i = 1, j = i + len - 1; j <= n; ++i, ++j){
               for(int k = i; k < j; ++k){
                   if(num[i][k] == num[k+1][j] && num[i][k])                    num[i][j] = num[i][k] + 1;            }        }    }    f[0] = 0;    for(int i = 1; i <= n; ++i){
           f[i] = i;        for(int j = 0; j < i; ++j){
               if(num[j+1][i])f[i] = min(f[i], f[j] + 1);        }    }    cout << f[n] << endl;}
   

转载地址：http://egkzi.baihongyu.com/