首页 > 代码库 > 即时战略游戏编队

即时战略游戏编队

2024-08-15 03:45:44   217人阅读

不打字了，直接贴图片吧！我只想说，这sb的题目，你把输入描写清楚好不，到底输不输入n啊，元素顺序是怎么样的啊，真扯淡，最后只过了40%，我都不知道怎么过的。输入顺序都是我自己瞎蒙的。

技术分享技术分享

你看他的输入，还用什么大括号括起来，到底是什么意思。

分析：简单的dp，有限背包问题。先计算所有数的总和，然后除以2，记为s，然后计算和为s的组合方式都多少种，符合题目描述的判重方式。

 1 /* 2 ID: y1197771 3 PROG: test 4 LANG: C++ 5 */ 6 #include<bits/stdc++.h> 7 #define pb push_back 8 #define FOR(i, n) for (int i = 0; i < (int)n; ++i) 9 #define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl10 typedef long long ll;11 using namespace std;12 typedef pair<int, int> pii;13 const int maxn = 1e6 + 10;14 int dp[11][maxn / 2];15 void solve() {16     int n;17     cin >> n;18     vector<int> cnt(n + 1), val(n + 1);19     int s = 0;20     for (int i = 1; i <= n; i++) {21         cin >> cnt[i];22 23     }24     for (int i = 1; i <= n; i++) {25         cin >> val[i];26         s += cnt[i] * val[i];27     }28     dp[0][0] = 1;29     s /= 2;30     for (int i = 1; i <= n; i++) {31         for (int k = 1; k <= cnt[i]; k++) {32             for (int j = 1; j <= s; j++) {33                 dp[i][j] += dp[i - 1][j];34                 //cout << j << " " << k * val[i] << endl;35                 if(j >= k * val[i])36                     dp[i][j] += dp[i - 1][j - k * val[i] ];37             }38         }39         //for (int j = 0; j <= s; j++)40             //cout << j << " " << dp[i][j] << endl;41     }42     cout << dp[n][s] << endl;43 44 }45 int main() {46     //freopen("test.in", "r", stdin);47     //freopen("test.out", "w", stdout);48     solve();49     return 0;50 }

 

即时战略游戏编队


联系
我们