太難的不會寫，因為真的不會，，，
1010 Lead of Wisdom
現在在題目單中已經可以找到6772Lead of Wisdom
題目大意
有t個測驗案例
每個案例首先會有n,k，n代表接下來的n行會有n把武器，每個武器是不同的種類，并且均擁有a，b，c，d四種屬性，k代表最多可以出現的武器種類最多有k種，
每種武器最多只能拿一把，也就是說當每一種武器都有的時候最多可以拿k把武器，如果有的武器種類沒有就不能拿這種，所以武器數一定 <= k
需要求的值為
分析
這題解法很暴力，就是把每一種情況的值都求出來然后依次比較找出最大值，不要擔心超時，因為時間復雜度在這種情況下是n的k/n次方，最壞的時候就是
3的16（50/3）次方，并不算太大，
這句話我也沒理解為什么會退化這么多，等我把搜索樹看了再試圖理解一下吧，，，
需要的工具：
cnt[k]:每一種型別的武器的數量
next[k]:每一種武器的下一種武器型別，主要是為了cnt[i] = 0的武器，存盤為它的下一個不為零的武器型別，方便直接dfs
一個結構體存盤每個武器及其四種屬性值，第一個下標代表武器屬性，第二個下標代表該種武器的第幾個（<cnt[i]）
struct war {
int a, b, c, d;
}item[55][55];
代碼（AC）
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<stdlib.h>
#include<vector>
#include<stack>
using namespace std;
const int MAX_N = 55;
int n, k;
long long ans;
int cnt[MAX_N];
int nxt[MAX_N];
struct war {
int a, b, c, d;
}item[MAX_N][MAX_N];
void solve(int x,int a,int b,int c,int d) {
if(x > k) {
//終止條件，到了最后一個屬性，計算并比較更新ans
long long temp = (long long)a * b * c * d;
if(temp > ans) ans = temp;
return;
}
if(!cnt[x]) {
solve(nxt[x],a,b,c,d);
return;
}
for(int i = 1; i <= cnt[x] ; i ++) {
solve(x + 1 , a + item[x][i].a , b + item[x][i].b , c + item[x][i].c , d + item[x][i].d );
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
while (T--) {
ans = 0;//每次重新計算清零答案
memset(cnt,0,sizeof(cnt));
cin >> n >> k;
int x;
while(n--) {
cin >> x;
cnt[x]++;
cin>>item[x][cnt[x]].a>>item[x][cnt[x]].b>>item[x][cnt[x]].c>>item[x][cnt[x]].d;
}
//處理next陣列
x = k + 1;
for(int i = k; i ; i--) {
nxt[i] = x;
if(cnt[i])
x = i;
}
solve(1,100,100,100,100);
cout<<ans<<endl;
}
return 0;
}
有個很莫名其妙的點，在放了這些頭檔案之后用next陣列會報編譯錯誤，改成nxt就ac了，好像是某個stl迭代器頭檔案里有一個next的同名方法，所以具體是哪一個我也不知道，
1001 Total Eclipse
原題鏈接
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/219729.html
標籤：區塊鏈
下一篇：練習1-遞推等