1.汤姆斯的天堂梦
题目链接：P1796 汤姆斯的天堂梦 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
此题类似于数字三角形，要求从顶点到三角形最后一行的最大距离和，dp
1 #include <bits/stdc++.h>
2 using namespace std;
3 const int N=105;
4 int n,k,f[N][N];
5 signed main()
6 {
7 ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
8 cin>>n;
9 memset(f,0x3f,sizeof f);
10 f[0][1]=0;
11 for(int i=1;i<=n;i++)
12 {
13 cin>>k;
14 for(int j=1;j<=k;j++)
15 {
16 int a,b;
17 cin>>a;
18 while(a!=0)
19 {
20 cin>>b;
21 f[i][j]=min(f[i][j],f[i-1][a]+b);
22 cin>>a;
23 }
24 }
25 }
26 int ans=0x3f3f3f3f;
27 for(int i=1;i<=k;i++)
28 {
29 ans=min(ans,f[n][i]);
30 }
31 cout<<ans<<endl;
32 return 0;
33 }
2.跑步
题目链接：P1806 跑步 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
本题类似于01背包，可以从将数组从二维优化成一维
1 #include <bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 const int N=510;
5 int ans;
6 int f[N][N];//f[i][j]表示总共跑i圈,最后一圈跑了j圈的方案数
7 //感觉就是01背包了
8 signed main()
9 {
10 ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
11 int n;
12 cin>>n;
13 for(int i=1;i<=n;i++)f[i][i]=1;
14 for(int i=1;i<=n;i++)
15 for(int j=1;j<i;j++)
16 for(int k=1;k<j&&k+j<=i;k++)
17 f[i][j]=f[i][j]+f[i-j][k];
18 for(int i=1;i<n;i++) ans+=f[n][i];
19 cout<<ans;
20 return 0;
21 }
3.砝码称重
题目链接：P8742 [蓝桥杯 2021 省 AB] 砝码称重 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
f[i][j]表示从前i个砝码选，总重量是j的bool值
1 #include <bits/stdc++.h>
2
3 using namespace std;
4
5 const int N=110,M=2e5+10,B=M/2;//f[i][j]表示从前i个砝码选，总重量是j的bool值
6
7 int n,m;//m表示所有方法的总重量
8 int w[N];
9 bool f[N][M];
10
11 signed main()
12 {
13 ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
14 cin>>n;
15 for(int i=1;i<=n;i++)cin>>w[i],m+=w[i];
16 f[0][B]=true;
17 for(int i=1;i<=n;i++)
18 for(int j=-m;j<=m;j++)
19 {
20 f[i][j+B]=f[i-1][j+B];
21 if(j-w[i]>=-m)f[i][j+B]|=f[i-1][j-w[i]+B];
22 if(j+w[i]<=m)f[i][j+B]|=f[i-1][j+w[i]+B];
23 }
24 int res=0;
25 for(int j=1;j<=m;j++)
26 if(f[n][j+B])res++;
27
28 cout<<res<<endl;
29 return 0;
30 }
4.遗址
题目链接：P1959 遗址 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
如果枚举四个点，三个点，都会TLE，可以降到N^2的复杂度，我们可以从其中的两个点，推测中其中另外两个点
#include<bits/stdc++.h>
using namespace std;
int vis[5005][5005];
int x[3005];
int y[3005];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> x[i] >> y[i];
vis[x[i]][y[i]] = 1;
}
int ans = 0;
for (int i = 1; i <= n; i++)
{
for (int j = i+1; j <= n; j++)
{
int x1 = x[i] - x[j];
int y1 = y[i] - y[j];
int x2 = x[i] + y1;
int y2 = y[i] - x1;
int x3 = x[j] + y1;
int y3 = y[j] - x1;
if (x2 < 1 || x2>5000 || y2 < 1 || y2>5000 || x3 < 1 || x3>5000 || y3 < 1 || y3>5000) continue;
if (vis[x2][y2] == 1 && vis[x3][y3] == 1)
{
ans = max(ans, x1 * x1 + y1 * y1);
}
}
}
cout << ans;
return 0;
}
5.环境治理
题目链接：P8794 [蓝桥杯 2022 国 A] 环境治理 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
Floyd和二分的综合题目
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define LL long long
4 LL temp,n, Q;
5 LL f[105][105],min_f[105][105],cut[105],dis[105][105];//cut为减少多少，dis表示减少后的
6 bool check(LL day)
7 {
8 temp = 0;//赋初值
9 LL times = day / n;
10 LL now = day%n;
11 for (int i = 1; i <= n; i++)
12 {
13 if (i <= now)cut[i] = times + 1;
14 else cut[i] = times;
15 }
16 /*for (int i = 1; i <= n; i++)
17 dis[i][i] = 0;*/
18 for (int i = 1; i <= n; i++)
19 {
20 for (int j = 1; j <= n; j++)
21 {
22 dis[i][j] = max(f[i][j] - cut[i] - cut[j], min_f[i][j]);
23 }
24 }
25 for (int k = 1; k <= n; k++)//Floyd模板
26 for (int i = 1; i <= n; i++)
27 for (int j = 1; j <= n; j++)
28 dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
29
30 for (int i = 1; i <= n; i++)
31 {
32 for (int j = 1; j <= n; j++)
33 {
34 temp += dis[i][j];
35 }
36 }
37 if (temp <= Q)return true;
38 else return false;
39 }
40 int main()
41 {
42 cin >> n>>Q;
43 for (int i = 1; i <= n; i++)
44 {
45 for (int j = 1; j <= n; j++)
46 {
47 cin >> f[i][j];
48 }
49 }
50 for (int i = 1; i <= n; i++)
51 {
52 for (int j = 1; j <= n; j++)
53 {
54 cin >> min_f[i][j];
55 }
56 }
57 LL left = 0, right = 1e9,mid/*,ans=1e9*/;
58 while (left<right)
59 {
60 mid = (left + right) / 2;
61 if (check(mid))/*ans=min(ans,mid),*/ right = mid;
62 else left = mid + 1;
63 }
64 if (left == 1e9)cout << "-1" << endl;
65 else cout << left << endl;
66 return 0;
67 }
标签：week11,int,LL,cin,ACM,ans,tie,预备队,105 From： https://www.cnblogs.com/Zac-saodiseng/p/17056281.html