T3

#include <bits/stdc++.h>
using namespace std;
int n,a[205];
long long dp[205][205];
       
long long cost(int i,int k,int j){
    return 1ll*a[i]*a[k+1]*a[j+1];
}
int main() 
{
    ios::sync_with_stdio(0);cin.tie(0);
       
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i+n]=a[i];
    }
       
    for(int len=2;len<=n;len++){
        for(int i=1;i+len-1<=2*n;i++){
            int j=i+len-1;
            for(int k=i;k<j;k++){
                dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+cost(i,k,j));
            }
        }
    }
       
    long long ans=0;
    for(int i=1;i<=n;i++){
        ans=max(ans,dp[i][i+n-1]);
    }
    cout<<ans;
    return 0;
}

T2

#include <bits/stdc++.h>
using namespace std;
int n,a[55];
long long cost(int i,int k,int j){
	return 1ll*a[i]*a[k]*a[j];
}
int main() 
{
    ios::sync_with_stdio(0);cin.tie(0);
	
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	long long dp[55][55];
	for(int i=1;i<=n;i++)dp[i][i]=0;
	for(int len=3;len<=n;len++){
		for(int i=1;i+len-1<=n;i++){
			int j=i+len-1;
			dp[i][j]=0x3f3f3f3f3f3f3f3f;
			for(int k=i+1;k<j;k++){
				dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+cost(i,k,j));
			}
		}
	}
	cout<<dp[1][n];
    return 0;
}

小视野区间dp T1

#include <bits/stdc++.h>
using namespace std;

int n, a[305];
int sum[305];
int dp[305][305];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }
    for (int i = 1; i <= n; i++) {
        dp[i][i] = 0;
    }
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            dp[i][j] = 0x3f3f3f3f;
            for (int k = i; k < j; k++) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1]);
            }
        }
    }

    cout << dp[1][n] << endl;
    return 0;
}

```cpp
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long a[73];
	long long x;
	cin >> x;
	for(int i = 0;i <= 63;i++) a[i] = pow(i,5);
	//for(int i = 1;i <= 63;i++) cout << a[i] << endl;
    long long b[3];
	bool y=0;
	for(int i = 0;i <=63;i++)
	{
		for(int j = 0;j <=63;j++)
		{
			b[1]=i,b[2]=j;
			if(a[i]+a[j]==x)
			{
				b[1]=i;b[2]=-j;
                y=1;
			}
			if(a[i]-a[j]==x)
			{
				b[1]=i;
                b[2]=j;
				y=1;
			}
			if(y==1)break;
		}
        if(y==1)break;
	}
	cout<<b[1]<<' '<<b[2];
	return 0;
}

C

#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,ans=0;
int h[100005];
bool tp[100005];
int main(){
	cin>>n>>m;
	for(int i=1; i<=100004; i++)tp[i]=1;
	for(int i=1; i<=n; i++){
		cin>>h[i];
	}
	for(int i=1; i<=m; i++){
		cin>>a>>b;
		if(h[b]>=h[a])tp[a]=0;
		if(h[a]>=h[b])tp[b]=0;
	}
	for(int i=1; i<=n; i++)if(tp[i])ans++;
	cout<<ans;
	return 0;
}

```cpp
#include<bits/stdc++.h>
using namespace std;
bool b[105];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int n,k,d;cin>>n>>k;
    
    for(int j=1;j<=k;j++){
        cin>>d;
        for(int i=1;i<=d;i++){
            int x;cin>>x;
            if(b[x]==0)n--;
            b[x]=1;
        }
    }
    cout<<n;
    return 0;
}

赛时讨论区↑

吴奕希 (hzzxwuyixi) @ 12 分钟前
https://www.gdgzoi.com/problem.php?cid=2830&pid=2

提示：该代码仅能获得70分，3个点TLE

#include<bits/stdc++.h>


using namespace std;
const int N=2005,V=505;
int n,v;
int m[N],w[N],s[N];
int dp[2][V];
int main(){
    cin>>n>>v;
    for(int i=1; i<=n; i++)cin>>m[i]>>w[i]>>s[i];
    for(int i=1; i<=n; i++){
        for(int j=1; j<=v; j++){
            for(int k=1; k<=m[i]; k++){
                if(j>=w[i]*k){
                    dp[1][j]=max(dp[1][j],dp[0][j-w[i]*k]+s[i]*k);
                }
            }
        }
        for(int j=1; j<=v; j++){
            dp[0][j]=dp[1][j];
        }
    }
    cout<<dp[1][v];
    return 0;
}```

P448题解 43.138.245.169/d/hongchang/p/P448/solution

https://www.gdgzoi.com/problem.php?cid=2829&pid=5

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 105,mod = 1e6+7;
int n,be,en,dp[N][N*10],a[N];
signed main(){
    ios::sync_with_stdio(false),cin.tie(0);
    cin >> n >> be >> en;dp[0][be] = 1;
    for(int i = 1 ; i < n ; i++){
        cin >> a[i];
        for(int j = 0 ; j <= en ; j++){
            if(dp[i-1][j]){
                int l = j-a[i],r = j+a[i];
                if(l >= 0) dp[i][l] = 1;
                if(r <= en) dp[i][r] = 1; 
            }
        }
    }
     
    for(int i = en ; i >= 0 ; i--) if(dp[n-1][i]) {cout << i;return 0;}
    cout << "-1";return 0;
    return 0;
}

https://www.gdgzoi.com/problem.php?cid=2829&pid=4

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 105,mod = 1e6+7;
int n,m,dp[N][N],a[N];
signed main(){
    ios::sync_with_stdio(false),cin.tie(0);
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i++) cin >> a[i];
    dp[0][0] = 1;
    for(int i = 1 ; i <= n ; i++){
        for(int j = 0 ; j <= m ; j++){
            if(dp[i-1][j] == 0 ) continue;
            for(int k = 0 ; k <= a[i]&&k+j<=m ; k++){
                (dp[i][j+k] += dp[i-1][j])%=mod;
            }
        }
    }
    cout << dp[n][m];
    return 0;
}

https://www.gdgzoi.com/problem.php?cid=2829&pid=3

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 105,inf = 0x3f3f3f3f;
int n,k,dp[N][N],a[N][N],put[N][N],maxx = -1;
signed main(){
    ios::sync_with_stdio(false),cin.tie(0);
    cin >> n >> k;
    for(int i = 1 ; i <= n ; i++){
        for(int j = 1 ; j <= k ; j++){
            cin >> a[i][j];
        }
    }
    memset(dp,-0x3f,sizeof dp);
    dp[0][0] = 0;
    for(int i = 1 ; i <= n ; i++){
        for(int p = i ; p <= k-n+i ; p++){
            for(int j = i-1 ; j < p ; j++){
                int pos = dp[i-1][j]+a[i][p];
                if(pos > dp[i][p]){
                    put[i][p] = j;
                    dp[i][p] = pos;
                }
            }
        }
    }
    int last = 0;
    for(int i = n ; i <= k ; i++){
        if(maxx < dp[n][i]){
            last = i;
            maxx = dp[n][i];
        }
    }
    vector<int>pos(n+1);
    for(int i = n ; i >= 1 ; i--){
        pos[i] = last;
        last = put[i][last];
    }
    cout << maxx << "\n";
    for(int i = 1 ; i <= n ; i++) cout << pos[i] << " ";
    return 0;
}

erweidonggui

https://www.gdgzoi.com/problem.php?cid=2829&pid=2

#include <bits/stdc++.h>
using namespace std;
int f[2005][2005];
int main()
{
    string a,b;
    cin >>a>>b;
      
    int n=a.size();
    int m=b.size();
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
        {
            if (a[i-1]==b[j-1])
                f[i][j]=f[i-1][j-1]+1;
            else
                f[i][j]=max(f[i-1][j],f[i][j-1]);
        }
    }
    cout <<f[n][m];
}

https://www.gdgzoi.com/problem.php?cid=2829&pid=1

#include <bits/stdc++.h>
using namespace std;
  
int main() {
    int n;
    cin >> n;
      
    int t[105][105];
      
  
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            cin >> t[i][j];
        }
    }
      
  
    for (int i = n - 1; i >= 1; i--) {
        for (int j = 1; j <= i; j++) {
            t[i][j] += max(t[i + 1][j], t[i + 1][j + 1]);
        }
    }
    cout << t[1][1] << endl;
      
    return 0;
}
  

https://www.gdgzoi.com/problem.php?cid=2829&pid=0

#include <bits/stdc++.h>


using namespace std;
int f[5009][5009];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<=n;i++)
    {
        f[0][i]=1;
    }
    for(int i=0;i<=m;i++)
    {
        f[i][0]=1;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            f[j][i]=(f[j-1][i]+f[j][i-1])%100000;
            //cout<<f[j][i]<<" ";
        }
        //cout<<endl;
    }
    cout<<f[m][n]%10000;
}```