NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2019高中組初賽
 D.分裁判問題

作者 主題: D.分裁判問題  (閱讀 1260 次)

LY02

  • 新手
  • *
  • 文章數: 2
    • 檢視個人資料
D.分裁判問題
« 於: 十一月 17, 2019, 10:31:04 pm »

這題給7秒基本上直接dfs枚舉所有可能,再把一些重複計算的部分排除就行了
代碼: [選擇]
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

int n,N;
bool vis[28];
long long val[28][28];
long long _max;
long long ans;
int qu[14],qu_2[14];
int f[14],f_2[14];
bool r;

void dfs(int pos,int pre){
if(r) return;
if(pos==n){
int t=0;
for(int i=0;i<N;i++){
if(vis[i]) continue;
qu_2[t]=i;
t++;
}

for(int i=0;i<n;i++){
if(f[i]!=qu_2[i]||f_2[i]!=qu[i]){
r=false;
break;
}
r=true;
return;
}
for(int i=0;i<n;i++){
f[i]=qu[i];
f_2[i]=qu_2[i];
}

long long tal=0;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
tal+=val[qu[i]][qu_2[j]];

if(tal>_max) _max=tal;
ans=_max;

return;
}
for(int i=pre;i<N;i++){
if(vis[i]) continue;
vis[i]=true;
qu[pos]=i;
dfs(pos+1,i);
vis[i]=false;
}
}

int main() {

cin>>n;
N=2*n;

memset(vis,false,sizeof(vis));
_max=-1;

for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
cin>>val[i][j];

r=false;

dfs(0,0);
cout<<ans<<endl;

return 0;
}
記錄

LY02

  • 新手
  • *
  • 文章數: 2
    • 檢視個人資料
Re: D.分裁判問題
« 回覆 #1 於: 十一月 17, 2019, 10:35:15 pm »

這個網站是不是都沒人了阿
記錄

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 238
    • 檢視個人資料
Re: D.分裁判問題
« 回覆 #2 於: 十一月 17, 2019, 10:40:01 pm »

這個網站是不是都沒人了阿

站長還活著,但沒什麼人會來了
曾經有一度這網站被NPSC官方網站列入參考資料的網站,
後來一次改版之後就被拿掉了,
然後人就越來越少了。
記錄

Felicity

  • 初級會員
  • **
  • 文章數: 24
    • 檢視個人資料
Re: D.分裁判問題
« 回覆 #3 於: 十一月 22, 2019, 08:03:15 pm »

請問
#define endl '\n'
這一列是不是可以省略?
直接寫
cout<<'\n';
是可以的嗎?
記錄

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 238
    • 檢視個人資料
Re: D.分裁判問題
« 回覆 #4 於: 十一月 23, 2019, 11:49:31 am »

請問
#define endl '\n'
這一列是不是可以省略?
直接寫
cout<<'\n';
是可以的嗎?

可以
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2019高中組初賽
 D.分裁判問題