长乐一中 Day 5 2023/7/19

背包问题

感觉今天上午的题稍微简单一点（

T1

link

水题。yx都会写我都会写。

排序之后直接完全背包即可。

code:

#include
#define int long long
using namespace std;
const int N=1e3+10,Max=0x3f3f3f3f3f3f3f;
int T,n,k,dp[N],ans;
struct fish{
    int t,p,a;
    bool operator <(const fish cmx)const{
        return a<cmx.a;
    }
}a[N];
signed main()
{
    freopen("frenzy.in","r",stdin);
    freopen("frenzy.out","w",stdout);
    scanf("%lld",&T);
    while (T--){
        ans=Max;
        dp[0]=0;
        scanf("%lld%lld",&n,&k);
        for (int i=1;i<=k;i++){
            dp[i]=Max;
        }
        for (int i=1;i<=n;i++){
            scanf("%lld%lld%lld",&a[i].a,&a[i].p,&a[i].t);
        }
        sort(a+1,a+1+n); 
        for (int i=1;i<=n;i++){
            for (int j=a[i].a;j=k){
                    ans=min(ans,dp[j]+a[i].t);
                    continue;
                }
                dp[j+a[i].p]=min(dp[j+a[i].p],dp[j]+a[i].t);
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

T2

link

赛时想出了一部分思路（排序后dp），但并没有推出转移条件。

一个数组 a能表示出所有不超过 \sum a 的正整数，当且仅当 a 排序之后，对于任意 1\le i\le n ，都有 \sum_{j<i}a_j+1\ge a_i 。

也就是说，对于已经确认是好的数组 s ，只需要判断 \sum s +1 是否大于等于 a_i ，就可以知道 s 中加入 a_i 后是否是好的了。

那么就可以直接转移。

code:

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+10,M=5e3,mod=1e9+7;
int n,a[N],dp[N][N],ans;
int main()
{
    freopen("subset.in","r",stdin);
    freopen("subset.out","w",stdout);
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    sort(a+1,a+1+n);
    dp[0][0]=1;
    for (int i=1;i<=n;i++){
        for (int j=0;j<=M;j++){
            dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;
            if (j+1>=a[i]){
                dp[i][min(j+a[i],M)]=(dp[i][min(j+a[i],M)]+dp[i-1][j])%mod;
            }
        } 
    }
    for (int i=1;i<=M;i++){
        ans=(ans+dp[n][i])%mod;
    }
    printf("%d",ans);
    return 0;
}

T3

link

感觉有点抽象，再看看。

区间DP

T1

(upd 2023-07-20 08:26:35 星期四)

link

其实就是很典型的区间dp，但是需要分类讨论。

本人分类讨论一直不行的

把每一段缩起来并记录颜色和长度，令 dp_{i,j} 表示消除 [i,j] 段的最小花费。

当 i 与 j 不在同一次操作中消除时，直接枚举 k 使得 [i,k] 和 [k+1,j] 被分别消除；

当 col[i]=col[j] 时，i 与 j 可以在同一次操作中消除。如果 i 与 j 的长度和大于等于3，它们可以直接在中间的部分被消除后直接消除，$dp{i,j}=min(dp{i+1,j-1})；否则需要在二者中间再加一个球，dp{i,j}=min(dp{i+1,j-1}+1)。当i,j与另一段k同时被消除（此时不论三者长度如何都可以连起来消除），枚举k$ 并消除它们中间的数即可。

code：

#include
using namespace std;
const int N=210;
int n,len[N],col[N],cnt,dp[N][N];
char s[N];
int main()
{
    freopen("zuma.in","r",stdin);
    freopen("zuma.out","w",stdout);
    scanf("%s",s+1);
    n=strlen(s+1);
    col[1]=s[1]-'0';
    len[1]=1;
    cnt=1;
    for  (int i=2;i<=n;i++){
        if (s[i]-'0'==col[cnt]){
            len[cnt]++;
        }
        else{
            len[++cnt]=1;
            col[cnt]=s[i]-'0';
        }
    }
    memset(dp,0x3f3f3f3f,sizeof dp);
    for (int i=1;i<=cnt;i++){
        if (len[i]==1){
            dp[i][i]=2;
        }
        else{
            dp[i][i]=1;
        }
    }
    for (int l=2;l<=cnt;l++){
        for (int i=1;i+l-1<=cnt;i++){
            int j=i+l-1;
            for (int k=i;k=3){
                    dp[i][j]=min(dp[i][j],dp[i+1][j-1]);
                }
                else{
                    dp[i][j]=min(dp[i][j],dp[i+1][j-1]+1);
                }
                for (int k=i+1;k<j;k++){
                    if (col[k]!=col[i]){
                        continue;
                    }
                    dp[i][j]=min(dp[i][j],dp[i+1][k-1]+dp[k+1][j-1]);
                } 
            }
        }
    }
    printf("%d",dp[1][cnt]);
    return 0;
}

感觉T2T3还是很抽象，再看看。