分數
| 題號 | 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
*/
