比较良心的膜你题。

一些定义：

$a$：所有小球的位置。

从小到大更新小球的位置，所以要先对 $a$ 排序，然后更新 $t$ 次，依次更新每个小球。

碰撞的情况很好判断，因为已经维护的 $a$ 的单调性，可能和当前第 $i$ 个球碰撞的一定只有 $a_{i+1}$。

// author: TMJYH09
// created on: 2022/05/25 21:01:07
#include <bits/stdc++.h>
using namespace std;

int L,n,t;
struct _{
    int pos,dir;
    int id;
}a[105];

int main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);
    cin>>n>>L>>t;
    for(int i=1;i<=n;i++){
        cin>>a[i].pos;a[i].dir=1;
        a[i].id=i;
    }
    sort(a+1,a+n+1,[](const _&x,const _&y){return x.pos<y.pos;});
    while(t--){
        for(int i=1;i<=n;i++){
            if(a[i].pos==L)a[i].dir=-1;
            if(a[i].pos==0)a[i].dir=1;
            if(a[i].pos==a[i+1].pos)a[i].dir=-a[i].dir,a[i+1].dir=-a[i+1].dir;
            a[i].pos+=a[i].dir;
        }
    }
    sort(a+1,a+n+1,[](const _&x,const _&y){return x.id<y.id;});
    for(int i=1;i<=n;i++)cout<<a[i].pos<<' ';
    return 0;
}

code 1

// author: TMJYH09
// create time: 2022/05/22 20:53:44
#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
const int N = 1005;
int n,m;
int f[N],g[N];

int main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);
    memset(f,0xcf,sizeof f);
    f[0]=0;g[0]=1;
    cin>>n>>m;
    for(int i=1,v,w;i<=n;i++){
        cin>>v>>w;
        for(int j=m;j>=v;j--){
            int mx=max(f[j],f[j-v]+w);
            int cnt=0;
            if(f[j]==mx)cnt+=g[j];
            if(f[j-v]+w==mx)cnt+=g[j-v];
            g[j]=cnt%mod;
            f[j]=mx;
        }
    }
    int ans=*max_element(f,f+m+1);
    int cnt=0;
    for(int i=0;i<=m;i++)
        if(ans==f[i])cnt=(cnt+g[i])%mod;
    cout<<cnt<<endl;
    return 0;
}

code 2

// author: TMJYH09
// create time: 2022/05/22 20:53:44
#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
const int N = 1005;
int n,m;
int f[N],g[N];

int main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);
    g[0]=1;
    cin>>n>>m;
    for(int i=1,v,w;i<=n;i++){
        cin>>v>>w;
        for(int j=m;j>=v;j--){
            int mx=max(f[j],f[j-v]+w);
            int cnt=0;
            if(f[j]==mx)cnt+=g[j];
            if(f[j-v]+w==mx)cnt+=g[j-v];
            g[j]=cnt%mod;
            f[j]=mx;
        }
    }
    int cnt=0;
    for(int i=0;i<=m;i++)
        if(f[i]==f[m])cnt=(cnt+g[i])%mod;
    cout<<cnt<<endl;
    return 0;
}

第一个是 y 总的，第二个是彩色铅笔大佬的，看不出区别呢

// author: TMJYH09
// create time: 2022/05/22 19:25:54
#include <bits/stdc++.h>
using namespace std;

const int N = 105;
int n,m;
struct edge{
    int to,nxt;
}e[N<<1];
int head[N],idx;
void add(int x,int y){e[++idx]={y,head[x]};head[x]=idx;}
int root;
int v[N],w[N],dp[N][N];

void dfs(int u){
    for(int i=head[u];i;i=e[i].nxt){
        int son=e[i].to;
        dfs(son);
        for(int j=m-v[u];j>=0;j--){
            for(int k=0;k<=j;k++){
                dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[son][k]);
            }
        }
    }
    for(int j=m;j>=v[u];j--)dp[u][j]=dp[u][j-v[u]]+w[u];
    for(int j=0;j<v[u];j++)dp[u][j]=0;
}

int main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1,s;i<=n;i++){
        cin>>v[i]>>w[i]>>s;
        if(s==-1)root=i;
        else add(s,i);
    }
    dfs(root);
    cout<<dp[root][m]<<endl;
    return 0;
}

// author: TMJYH09
// create time: 2022/05/22 16:23:41
#include <bits/stdc++.h>
using namespace std;

int n,m;
int dp[1005];

int main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1,v,w,s;i<=n;i++){
        cin>>v>>w>>s;
        if(s==0){
            for(int j=v;j<=m;j++)dp[j]=max(dp[j],dp[j-v]+w);
        }else{
            if(s==-1)s=1;
            for(int k=1;k<=s;k<<=1){
                for(int j=m;j>=k*v;j--){
                    dp[j]=max(dp[j],dp[j-k*v]+k*w);
                }
                s-=k;
            }
            if(s){
                for(int j=m;j>=s*v;j--){
                    dp[j]=max(dp[j],dp[j-s*v]+s*w);
                }
            }
        }
    }
    cout<<dp[m]<<endl;
    return 0;
}

// author: TMJYH09
// create time: 2022/05/20 21:18:26
#include <bits/stdc++.h>
using namespace std;

const int N = 105, M = 250005;
int n;
int a[N],dp[M];

void solve(){
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    sort(a,a+n);
    memset(dp,0,sizeof dp);
    int ans=0;
    dp[0]=1;
    for(int i=0;i<n;i++){
        if(!dp[a[i]])ans++;
        for(int j=a[i];j<=a[n-1];j++){
            dp[j]+=dp[j-a[i]];
        }
    }
    cout<<ans<<endl;
}

int main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);
    int _;cin>>_;while(_--)solve();
    return 0;
}

// author: TMJYH09
// create time: 2022/05/19 19:17:11
#include <bits/stdc++.h>
using namespace std;

int n,m;
int a[15];
long long dp[3005];

int main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>a[i];
    dp[0]=1;
    for(int i=0;i<n;i++)
        for(int j=a[i];j<=m;j++)
            dp[j]+=dp[j-a[i]];
    cout<<dp[m]<<endl;
    return 0;
}

// author: TMJYH09
// create time: 2022/05/18 22:47:37
#include <bits/stdc++.h>
using namespace std;

using PII = pair<int,int>;

const int N = 35005,M = 65;
PII main_item[N];
vector <PII> appendix[M];
int n,m;
int dp[N];

int main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        int v,p,q;
        cin>>v>>p>>q;
        if(!q)main_item[i]={v,v*p};
        else appendix[q].push_back({v,v*p});
    }
    #define v first
    #define w second
    for(int i=1;i<=n;i++)
        for(int j=m;j>=0;j--){
            for(int k=0;k<(1<<appendix[i].size());k++){
                int v=main_item[i].v,w=main_item[i].w;
                for(int u=0;u<appendix[i].size();u++){
                    if(k >> u & 1){
                        v+=appendix[i][u].v;
                        w+=appendix[i][u].w;
                    }
                }
                if(j>=v)dp[j]=max(dp[j],dp[j-v]+w);
            }
        }
    cout<<dp[m]<<endl;
    return 0;
}