两个dp题

D题链接

C题链接

D题：

        很容易贪心的想到alice一定是取所存不同数字里的最小值，bob就是想办法尽量多拿掉alice之后数字。这样问题就转化成有n种物品，每个物品有a【i】个，bob每次取空一个物品，或者不取，最后可以取得的最多物品数。这就可以看出来是背包问题，我们令dp【i】【j】表示前i个物品bob取j个物品的最小操作数。

        我们枚举每个物品，表示bob现在要清空这个物品。我们考虑bob什么情况下才可以在alice拿到第i个物品前拿完第i个物品。我们假设bob之前拿了j-1个物品，合法的情况下他已经花了dp【i-1】【j-1】个次数。因为bob每花一次次数，alice就会拿一个物品，bob用了dp【i-1】【j-1】次次数，那么alice就已经拿了dp【i-1】【j-1】个物品，且bob拿了j-1个物品，所以在bob开始取第i个物品之前(且先手是alice，alice还没取)，alice和bob总的取的物品已经有dp【i-1】【j-1】+j-1个了（我们假设alice取一次，bob取一次，bob取第dp【i-1】【j-1】次的时候，其实alice已经取完属于她的第dp【i-1】【j-1】个物品了，当bob取完第dp【i-1】【j-1】次操作后，下次是alice先手，这时候alice取的是属于她的第【i-1】【j-1】+1个物品，而bob取了j-1个物品）。

        在第dp【i-1】【j-1】+j-1+1个物品到第i个物品之间有i-（dp【i-1】【j-1】+j-1+1）（不能+1，因为alice不能取到第i个物品）个物品可以让alice取，也就是说留给bob取第i个物品的次数只有i-（dp【i-1】【j-1】+j-1+1）次，如果a【i】>i-（dp【i-1】【j-1】+j-1+1）bob就无法取走第i个物品，也就是说dp不能从j-1转移到j，将式子简化一下就是i-j<dp【i-1】【j-1】+a【i】时无法转移，那么合法的转移条件就是i-j>=dp【i-1】【j-1】+a【i】。

        那么转移方程就是dp【i】【j】=dp【i-1】【j-1】+a【i】表示从i物品之前已经取了j-1个物品的最小操作数加上取第i个物品的操作。因为这个转移方程是有条件的，所以我们每次都假设不选当前物品，dp【i】【j】=dp【i-1】【j】。注意，这里一定要保证所有dp状态和dp值都要合法的，不然直接转移会出问题。比如1 2 3 4 4，bob最大操作数只能删掉2或者3，但如果dp转移不合法的话，dp【3】【2】会更新成2，但实际上dp【3】【2】应该是inf的，因为它并不能转移到（bob不能在第3个物品前取完2个物品），然后dp【3】【2】=2又会影响到dp【4】【2】，因为dp【i】【j】可以直接从dp【i-1】【j】转移，这样dp【4】【2】=2，而这时候2又小于等于4-2（i-j），反而把dp【3】【2】变合法了，这是因为直接转移的话相当于给前面一个状态的bob又加了一次操作数，但是实际上前面的状态是没有这个操作数的。

        所以我们在状态转移的时候先保证每个合法状态的转移，只有满足了转移条件才能让该状态从前面状态转移。

        注释的两行就是上述的错误转移方程。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
const int inf=0x3f3f3f3f;
const int N=2e5+10;
const int mod=1e9+7;
const ll INF=2e9+10;
mt19937_64 rd(23333);
uniform_real_distribution<double> drd(0.000001,0.99999);void solve(){vector<int> a;int n;cin>>n;map<int,int> cnt;while(n--){int x;cin>>x;cnt[x]++;}for(auto const &[k,v]:cnt){a.push_back(v);//选出不同且单调上升的数 }n=a.size();vector<vector<int> > dp(n+1,vector<int>(n+1,inf));int maxx=0;for(int i=0;i<=n;i++)dp[i][0]=0;for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){//dp[i][j]=min(dp[i-1][j],dp[i-1][j-1]+a[i-1]);//dp【i-1】【j-1】+a【i-1】可能不合法，不能直接转移dp[i][j]=dp[i-1][j]; if(dp[i-1][j-1]+a[i-1]<=i-j){//if(dp[i][j]<=i-j){//和上述错误转移一样dp[i][j]=min(dp[i][j],dp[i-1][j-1]+a[i-1]);maxx=max(maxx,j);}}}cout<<n-maxx<<endl;
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t=1;cin>>t;while(t--){solve();}return 0;
}

C题：

        设dp【i】【j】为前i个数操作j次的最小和。可以发现从dp【i-1】【j-1】转移的话并不能确定a【i-1】是否是dp【i-1】【j-1】中操作数之一，也就是说a【i-1】的状态我们并不能确定，所以不能直接转移。但我们发现k很小，也就是说第i个位置需要判断的前面几个数是否发生变化的数量很少，我们可以直接暴力把这些位置的所有状态都转移。也就是说dp【i】【j】我们可以考虑j里面有几次是会影响到i-1这个位置，也就是从i-1往前多少个连续数我们都采用了操作，这样最多只要判断d次，容易知道当我们操作了连续d次，那么这些数都可以变成这d个数里的最小数，所以我们直接记录d区间最小数，然后mi*（d+1）（因为是从i+d位置从前操作d次，d次可以取d+1个数的min）就是这几个数的贡献，也就是他们的和，然后再加上d区间前面的选操作j的dp值即可（dp【i-1】【j】），因为我们是不考虑第i位变化的，所以我们要从dp【i-1】转移，这样i的值就不变了。

        由于我们要记录d区间的最小值，我们可以枚举到i的时候然后慢慢增加d，然后每次与a【i+d】取min就是这d区间最小值了，可以避免重复计算。我们从i计算i+d区间的min时，算的是dp【i+d】的值，因为dp状态是从i+d往前连续操作d次，注意，因为我们枚举的连续区间，也就是说区间左端点是不会再被它之前的位置影响，也就是说从i位置往后枚举，a【i】就是a【i】，不会被a【i-1】影响，所以我们要从dp【i-1】转移，从dp【i】转移的话a【i】的值不确定 。

        其实就是枚举所有a【i-1】的情况，枚举所有转移状态，然后暴力转移。

        最后dp【n】【k】即是答案。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
const int inf=0x3f3f3f3f;
const int N=2e5+10;
const int mod=1e9+7;
const ll INF=2e9+10;
mt19937_64 rd(23333);
uniform_real_distribution<double> drd(0.000001,0.99999);int n,k;void solve(){cin>>n>>k;int maxx=0;vector<int> a(n+2);for(int i=1;i<=n;i++)cin>>a[i];vector<vector<int> > dp(n+1,vector<int>(k+1,1e18));for(int i=0;i<=k;i++)dp[0][i]=0;for(int i=1;i<=n;i++){for(int j=0;j<=k;j++){//j表示枚举的i-1前（没有i）的操作数 int mi=inf;for(int d=0;d+j<=k&&i+d<=n;d++){//d表示往后的操作数 mi=min(mi,a[i+d]);//往前j，往后只有k-j，j+d就是总 dp[i+d][j+d]=min(dp[i+d][j+d],dp[i-1][j]+(d+1)*mi);}}}cout<<dp[n][k]<<endl;//cout<<*min_element(dp[n].begin(),dp[n].end())<<endl;
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t=1;cin>>t;while(t--){solve();}return 0;
}