分数
| 题号 | T1 | T2 | T3 | T4 | T5 | T6 | T7 | 总分 |
|---|---|---|---|---|---|---|---|---|
| 分数 | 100 | 100 | 100 | 20 | 100 | 100 | 64 | 584 |
分析
T1
模板，讲烂了
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int maxn=1e6+5,mod=1e9+7,inf=1e18;
int n,a[maxn],dp[maxn];
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int maxi=-inf;
for(int i=1;i<=n;i++){
dp[i]=1;
for(int j=1;j<i;j++){
if(a[j]<a[i]){
dp[i]=max(dp[i],dp[j]+1);
}
}
maxi=max(maxi,dp[i]);
}
cout<<maxi<<endl;
return 0;
}
T2
二维DP模板，也讲烂了
Tip：注意行列为偶数时不能走
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int maxn=1e3+5,mod=1e9+7,inf=1e18;
int n,m,dp[maxn][maxn];
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
dp[1][1]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(i==1&&j==1)continue;
if(i%2==0&&j%2==0)continue;
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
cout<<dp[n][m]<<endl;
return 0;
}
T3
有\(10^{-9}\)点意思。
- 定义状态：\(dp_i\)表示恰好得到\(i\)个字的最少操作次数
- 答案：\(dp_n\)
- 状态转移方程：
①：从\(i-1\)转移过来：\(dp_{i-1}+1\)
②：当\(i\)为偶数时，从\(\frac{i}{2}\)转移过来：\(dp_{\frac{i}{2}}+1\)
答案即：
(1)\(i\mod 2=1\)，\(dp_i=dp_{i-1}+1\)
(2)\(i\mod 2=0\)，\(dp_i=\min(dp_{i-1}+1,dp_{\frac{i}{2}}+1)\) - 边界：\(dp_1=1\)
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int maxn=1e6+5,mod=1e9+7,inf=1e18;
int n,dp[maxn];
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
memset(dp,0x3f,sizeof(dp));
dp[1]=0;
for(int i=2;i<=n;i++){
dp[i]=min(dp[i],dp[i-1]+1);
if(i%2==0){
dp[i]=min(dp[i],dp[i/2]+1);
}
}
cout<<dp[n]<<endl;
return 0;
}
T4
典例题，只不过将01背包的模板\(c\)数组改为打赢一个值，打输一个值而已
注意：这里由于前面的与后面的有关，所以不能改成一个一维数组的优化（喜提20分……）
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int maxn=1e3+5,mod=1e9+7,inf=1e18;
int n,m,win[maxn],lose[maxn],use[maxn],dp[maxn][maxn];
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>lose[i]>>win[i]>>use[i];
}
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
if(j>=use[i]){
dp[i][j]=max(dp[i-1][j]+lose[i],dp[i-1][j-use[i]]+win[i]);
}
else{
dp[i][j]=dp[i-1][j]+lose[i];
}
}
}
cout<<dp[n][m]*5<<endl;
return 0;
}
T5
这里我用记搜写的
定义\(dfs(pos,x)\)表示第\(x\)此传球在第\(pos\)个人手上
那么只要判断x=1时pos是否也等于1即可
注意，环形，所以1号左边是\(n\)号，\(n\)号右边是一号
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int maxn=1e3+5,mod=1e9+7,inf=1e18;
int n,m,dp[maxn][maxn],ans[maxn];
int gl(int x){
if(x==1){
return n;
}
return x-1;
}
int gr(int x){
if(x==n){
return 1;
}
return x+1;
}
int dfs(int pos,int x){
if(x==1){
if(pos==1){
return 1;
}
return 0;
}
if(dp[pos][x]!=-1){
return dp[pos][x];
}
int anss=dfs(gl(pos),x-1)+dfs(gr(pos),x-1);
dp[pos][x]=anss;
return anss;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
memset(dp,-1,sizeof(dp));
cout<<dfs(1,m+1)<<endl;
return 0;
}
T6
最大正方形的改版，只不过加一个维度表示右下角的数是1还是0
如果数是0，则答案需要：
左边的以1为右下角的满足条件的正方形边长与
上方的以1为右下角的满足条件的正方形边长与
左上角的以0为右下角的满足条件的正方形边长
作比较，取最小值
同理，如果数是1，则答案需要：
左边的以0为右下角的满足条件的正方形边长与
上方的以0为右下角的满足条件的正方形边长与
左上角的以1为右下角的满足条件的正方形边长
作比较，取最小值
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int maxn=2e3+5,mod=1e9+7,inf=1e18;
int n,m,a[maxn][maxn],dp[maxn][maxn][2];
signed main(){
// freopen("test.in","r",stdin);
// freopen("test.out","w",stdout);
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char c;
cin>>c;
a[i][j]=c-'0';
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dp[i][j][a[i][j]]=1;
}
}
int maxi=-inf;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]==1){
dp[i][j][1]=min(dp[i-1][j][0],min(dp[i][j-1][0],dp[i-1][j-1][1]))+1;
maxi=max(maxi,dp[i][j][1]);
}
else{
dp[i][j][0]=min(dp[i-1][j][1],min(dp[i][j-1][1],dp[i-1][j-1][0]))+1;
maxi=max(maxi,dp[i][j][0]);
}
}
}
cout<<maxi<<endl;
return 0;
}
T7
同样也是最大正方形的改版
可以发现，如果想要从一个正方形扩大，需要右下角为1，其余都为0，定义两个数组，分别表示一个位置左边0的个数与上方0的个数（包括自己）
则答案为：
左边的以0为的个数与
上方的以0的个数与
左上角的以1为右下角的满足条件的正方形边长
作比较，取最小值
坑点：
由于是对角线，所以左右两边的对角线都要考虑，右边同理
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int maxn=2e3+5e2+5,mod=1e9+7,inf=1e18;
int n,m,a[maxn][maxn],dp[maxn][maxn],pd[maxn][maxn][2],dp1[maxn][maxn];
signed main(){
// freopen("test.in","r",stdin);
// freopen("test.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char c;
cin>>c;
a[i][j]=c-'0';
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]==1){
dp[i][j]=1;
}
}
}
// cout<<"haha1";
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]==0){
pd[i][j][0]=pd[i][j-1][0]+1;
pd[i][j][1]=pd[i-1][j][1]+1;
}
}
}
int maxi=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]==1){
dp1[i][j]=min(dp1[i-1][j-1],min(pd[i][j-1][0],pd[i-1][j][1]))+1;
maxi=max(maxi,dp1[i][j]);
}
}
}
// cout<<"haha2";
memset(pd,0,sizeof(pd));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]==1){
dp1[i][j]=1;
}
}
}
for(int i=1;i<=n;i++){
for(int j=m;j>=1;j--){
if(a[i][j]==0){
pd[i][j][0]=pd[i][j+1][0]+1;
pd[i][j][1]=pd[i-1][j][1]+1;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]==1){
dp1[i][j]=min(dp1[i-1][j+1],min(pd[i][j+1][0],pd[i-1][j][1]))+1;
maxi=max(maxi,dp1[i][j]);
}
}
}
cout<<maxi;
return 0;
}
/*
4 4
1 0 0 1
0 0 1 0
0 1 0 1
1 0 0 0
*/