异星矿区

2026-08-10 20:43:21

发布于：广东

89阅读

0回复

0点赞

https://www.acgo.cn/problemset/info/125628?teamCode=2042058713337094144
BFS题解

//dp[i][j]
//dp[i+1][j]+=d[i][j];
//dp[i][j+1]+=d[i][j];
#include<bits/stdc++.h>
using namespace std;
const int N=500+10;
#define ll long long
ll a[N][N],dp[N][N];
bool vis[N][N][12][2];//vis[i][j][k][d] 在d方向走k次走到(i,j)坐标是否到达
ll res[N][N][12][2];// 在d方向走k次走到(i,j)坐标对应的答案
//step：沿一个方向走的步数，dire：方向 0:向右，1：向下
int n,m,k;
bool check(int x,int y){
    if(x<1||x>n||y<1||y>m)return false;
    return true;
}
struct Node{
    int x,y;
    int step,dire;

};
ll ans=-1;
void bfs(){
    queue<Node>que;
    que.push({1,1,0,0});
    vis[1][1][0][0]=1;//为起点打上标记   //分层图
    res[1][1][0][0]=a[1][1];
    while(que.size()){
        auto cur=que.front();que.pop();
        // cout<<cur.x<<' '<<cur.y<<' '<<cur.step<<' '<<cur.dire<<' '<<res[cur.x][cur.y][cur.step][cur.dire]<<endl;;
        if(cur.x==n&&cur.y==m){
            ans=max(ans,res[cur.x][cur.y][cur.step][cur.dire]);
        }
        //继续沿着方向走
        if(cur.step<k){
            int nx=cur.x,ny=cur.y;
            if(cur.dire==0)ny++;
            else nx++;
            if(check(nx,ny)){
                if(vis[nx][ny][cur.step+1][cur.dire]==0){
                    que.push({nx,ny,cur.step+1,cur.dire});
                    vis[nx][ny][cur.step+1][cur.dire]=1;
                }
                res[nx][ny][cur.step+1][cur.dire]=max(res[nx][ny][cur.step+1][cur.dire],
                res[cur.x][cur.y][cur.step][cur.dire]+a[nx][ny]);
            }
        }
        //拐弯
        // if(cur.step!=k){
            int nx=cur.x,ny=cur.y;
            if(cur.dire==1)ny++;
            else nx++;
            if(check(nx,ny)){
                if(vis[nx][ny][1][1-cur.dire]==0){
                    que.push({nx,ny,1,1-cur.dire});
                    vis[nx][ny][1][1-cur.dire]=1;
                    
                }
                res[nx][ny][1][1-cur.dire]=max(res[nx][ny][1][1-cur.dire],
                res[cur.x][cur.y][cur.step][cur.dire]+a[nx][ny]);
            }
        // }
    }
}
void solve(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
        cin>>a[i][j];
    }
    bfs();
    cout<<ans<<endl;
}
int main(){
    int t=1;
    freopen("y.in", "r", stdin);
    freopen("y.out", "w", stdout);
    // cin>>t;
    while(t--){
        solve();
    }
}

动态规划:

//dp[i][j]
//dp[i+1][j]+=d[i][j];
//dp[i][j+1]+=d[i][j];
#include<bits/stdc++.h>
using namespace std;
const int N=500+10;
#define ll long long
ll dp[N][N][12][2];
ll a[N][N];
int n,m,k;

ll ans=-1;
void solve(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
        cin>>a[i][j];
    }
    // dp[1][1][5][0];
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    for(int step=0;step<=k;step++)
    for(int dire=0;dire<2;dire++){
        dp[i][j][step][dire]=-1e18;
    }
    dp[1][1][0][0]=a[1][1];//起点保留
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    for(int step=0;step<=k;step++)
    for(int dire=0;dire<2;dire++){
        if(dp[i][j][step][dire]==-1e18)continue;
        if(i==n&&j==m)ans=max(ans,dp[i][j][step][dire]);
        if(step<k){
            int nx=i,ny=j;
            if(dire==0)ny++;else nx++;
            dp[nx][ny][step+1][dire]=max(dp[nx][ny][step+1][dire],dp[i][j][step][dire]+a[nx][ny]);
        }
        int nx=i,ny=j;
        if(dire==1)ny++;else nx++;
        dp[nx][ny][1][1-dire]=max(dp[nx][ny][1][1-dire],dp[i][j][step][dire]+a[nx][ny]);
    }
    cout<<ans<<endl;
}
int main(){
    int t=1;
    freopen("y.in", "r", stdin);
    freopen("y.out", "w", stdout);
    // cin>>t;
    while(t--){
        solve();
    }
}

//T125627.宿命印记
https://www.acgo.cn/problemset/info/125627?teamCode=2042058713337094144

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
ll a[N];
// string s="ABCDE";

ll n,ans=0;
ll pre[N];//求前缀和 
void solve(){
	ans=0;
    cin>>n;
    for(int i=1;i<=n;i++){
    	cin>>a[i];
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++){
		pre[i]=pre[i-1]+a[i];
	}
	//1 2 3 4 5 6 7
	//1000-1+1000-2+1000-3
	//3000-(1+2+3)
	for(int i=1;i<=n;i++){
		//前缀和
		//pre[i]=pre[i-1]+a[i]; 
		ll atk=0;//攻击的总量 
//		for(int j=i+1;j<=n;j++)atk+=a[j];[i+1,n]
		atk=pre[n]-pre[i];
		ll dee=0;//防御的总量
//		for(int j=1;j<=i;j++)dee+=1000-a[j];
		dee=i*1000-pre[i];
		ans=max(ans,atk*dee); 
	}

	cout<<ans<<endl;

}
//sum(n)<=
int main(){
    freopen("s.in","r",stdin);
    freopen("s.out","w",stdout);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define all(a) a.begin(),a.end()
#define fr(a,i,n) for(int i=a;i<=n;i++)
#define fe(a,i,n) for(int i=n;i>=a;i--)
#define endl "\n"
template<typename T1,typename T2>
istream &operator>>(istream &in,pair<T1,T2> &a){return in>>a.first>>a.second;};
template<typename T1,typename T2>
ostream &operator<<(ostream&,pair<T1,T2> &a){return cout<<a.first<<' '<<a.second;};
template<typename T>
istream &operator>>(istream &in,vector<T>&v){T x;in>>x;v.push_back(x);return in;};
template<typename T>
T rmin(T &a,T b){if(a>b)a=b;return a;}
template<typename T>
T rmax(T &a,T b){if(a<b)a=b;return a;}
string YES="YES",Yes="Yes",yes="yes",NO="NO",No="No",no="no";
const int N=4e5+10,M=1e6+10,mod=1e9+7;
string s;
int n,m,k;
int a[N],b[N];
void solve(){
    
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    fr(1,i,t){
        solve();
    }
}