题解仅供参考！！！不要抄袭！！！(doge)
题解数量:11
跳转至目录
海盗队长信奥怪猫侠2
详细题解以及思路点击此处跳转
乘法游戏
#include <bits/stdc++.h>
using namespace std;
const int MAXN=105;
int f[MAXN][MAXN],a[MAXN],n,ans;
int dp(int x,int y){
if(y-x==1) return 0;
if(f[x][y]!=f[0][0]) return f[x][y];
for(int i=x+1;i<y;i++) f[x][y]=min(f[x][y],dp(x,i)+dp(i,y)+a[x]*a[i]*a[y]);
return f[x][y];
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
memset(f,127,sizeof(f));
cout<<dp(1,n);
return 0;
}
演讲大厅安排
见gsx的GF2025B3背包大合集
工作分配问题
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[1005][1005],n,ans=INT_MAX;//数组初始化
bool b[105];//判重数组
void dfs(int sum,int dep){
if(sum>ans) return;
if(dep>n){//结束条件
ans=min(sum,ans);//取最小值
return;
}
//int min1=INT_MAX;
for(int i=1;i<=n;i++){
if(b[i]==false){//判重
b[i]=true;//已经检查过
dfs(sum+a[dep][i],dep+1);//递归
b[i]=false;//取消检查
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)cin>>a[i][j];
dfs(0,1);
cout<<ans<<endl;//答案
return 0;
}
// /files
过河卒
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=5055;
ll dp[MAXN][MAXN];
int n,m,x,y;
bool add(int i,int j,int x,int y){//这一个函数来判断卒是否在马移动范围内
return i==x && j==y
|| i==x-2 && j==y-1 || i==x-2 && j==y+1
|| i==x-1 && j==y-2 || i==x-1 && j==y+2
|| i==x+1 && j==y-2 || i==x+1 && j==y+2
|| i==x+2 && j==y-1 || i==x+2 && j==y+1;
}
int main(){
ios::sync_with_stdio(0);//加快时间
cin.tie(0);//加快时间
cout.tie(0);//加快时间
cin>>n>>m>>x>>y;
n++;m++;x++;y++;
dp[0][1]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(!add(i,j,x,y)) dp[i][j]=dp[i][j-1]+dp[i-1][j];
cout<<dp[n][m];
return 0;
}
乘积最大
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll num[15],dp[15][15],mg[15][15];//数组初始
ll n,k,x;
int main(){
cin>>n>>k>>x;
k++;
int m=n;
while(x>0){
num[m--]=x%10;//数组每一位初始化
x/=10;
}
for(int i=1;i<=n;i++){
ll mlp=mg[i][i]=num[i];
for(int j=i+1;j<=n;j++){
mlp=mlp*10+num[j];//算当前值
mg[i][j]=mlp;//保存
}
}
for(int i=1;i<=n;i++) dp[i][1]=mg[1][i];
for(int kk=2;kk<=k;kk++)
for(int i=1;i<=n;i++)
for(int j=1;j<i;j++)
dp[i][kk]=max(dp[j][kk-1]*mg[j+1][i],dp[i][kk]);//取最大
cout<<dp[n][k];//答案
return 0;//AC！！！
}
滑雪
#include<bits/stdc++.h>
using namespace std;
int skl[105][105],sum[105][105];
int dx[]={0,-1,1,0,0};
int dy[]={0,0,0,-1,1};
int r,c,ans=INT_MIN;
bool line(int x,int y){
if(x<1||y<1||x>r||y>c)return 0;//判断是否违法出界
else return 1;
}
int dfs(int x/*行*/,int y/*列*/){
if(sum[x][y]>0)return sum[x][y];
sum[x][y]=1;
int len=0;
for(int i=1;i<=4;i++){
int newx=x+dx[i];
int newy=y+dy[i];
if(line(newx,newy)&&skl[newx][newy]<skl[x][y]){//判断
len=max(len,dfs(newx,newy));//滑行长度
}
}
return sum[x][y]=len+1; //长度
}
int main(){
cin>>r>>c;
for(int i=1;i<=r;i++){//行
for(int j=1;j<=c;j++){//列
cin>>skl[i][j];//输入
}
}
for(int i=1;i<=r;i++){
for(int j=1;j<=c;j++){
ans=max(ans,dfs(i,j));//取最大
}
}
cout<<ans;//答案
}
装载问题
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[1005],n,x,ans;
void dfs(int sum,int dep){
if(sum>x) return ;//结束条件1
ans=max(ans,sum);//取最大
if(dep>n) return;//结束条件2
dfs(sum+a[dep],dep+1);//选
dfs(sum,dep+1);//不选
}
int main(){
cin>>n>>x;//输入
for(int i=1;i<=n;i++) cin>>a[i];//输入
dfs(0,1);//初始总和为0，dep层级为1，因为已进行1次了
cout<<ans<<endl;//答案
return 0;
}
// /files
迷宫问题
#include <bits/stdc++.h>
using namespace std;
int n,a[1005][1005],cnt=0;
bool b[1005][1005];
int dx[8]{-1,-1,-1,0,0,1,1,1};//经典上下左右
int dy[8]{-1,0,1,-1,1,-1,0,1};//上述
void dfs(int x,int y){
if(x==1 && y==n){//是否到达终点
cnt++;//方案次数
return;
}
for(int j=0;j<8;j++){
int nx=x+dx[j];//新x坐标
int ny=y+dy[j];//新y坐标
if(x>=1 && x<=n && y>=1 && y<=n && a[nx][ny]==0 && b[nx][ny]==false){//判断是否违法越界
b[x][y]=true;//判重
dfs(nx,ny);//递归
b[x][y]=false;//取消
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) cin>>a[i][j];
}
//输入
b[1][1]=true;//注意这个别忘了加，初始点遍历过了
dfs(1,1); //初始点
cout<<cnt;//答案
return 0;//AC！！！
}
// /files
GCD和LCM是好朋友(数据加强版)
#include<bits/stdc++.h>
#define ll unsigned long long//数据太大了
#define AC return 0
using namespace std;
ll x,y,cnt;
ll gcd(ll x,ll y){//检查k是否是y约数
return y?gcd(y,x%y):x;
}
int main(){
cin>>x>>y;
for(ll k=1;k<=sqrt(y);k++){//遍历所有可能的k值
if(y%k==0){
if(gcd(k,y/k*x)==x){
cnt++;
}
if(y/k!=k){
if(gcd(y/k,k*x)==x){
cnt++;
}
}
}
}
cout<<cnt;//答案
AC;//等价 return 0;
}
N皇后问题
#include <bits/stdc++.h>
using namespace std;
int n,ans[15];
bool b[15],zx[20],yx[20],out=false;//数组
void dfs(int dep){
if(dep>n){
for(int i=1;i<=n;i++) cout<<setw(5)<<ans[i];//注意宽敞
cout<<endl;
out=true;//有方案
return;
}
for(int i=1;i<=n;i++){
if(!b[i]&&!zx[dep+i]&&!yx[i-dep+n]){//判断是否违法出界
b[i]=zx[dep+i]=yx[i-dep+n]=true;//这里用来判重
ans[dep]=i;//答案储存
dfs(dep+1);//递归
b[i]=zx[dep+i]=yx[i-dep+n]=false;//取消
}
}
}
int main(){
cin>>n;
dfs(1);//dep层级从1~n
if(out==false) cout<<"no solute!";//无方案
return 0;//AC！！！
}
// /files
/*
@*@@
@@@*
*@@@
@@*@
*/
//呃呃呃这是根据题目做的
标准目录页
gf24118
LV 8
@
2025-7-16 15:26:53