1007 Maximum Subsequence Sum (25 分)

• 題意 ：注意最后輸出的不是索引而是在那個索引的數(shù)
• 思路 ：f為當前的假設(shè)開始指針，每一次累加到sum，如果sum大于res，就更新res，開始指針和結(jié)束指針；如果sum小于0，說明這段都不要了，那么sum清零，f從下一位開始

#include <iostream>using namespace std;const int N = 1e4 + 10;int num[N];int main() {int n;cin >> n;for (int i = 0; i < n; i ++ ) cin >> num[i];int res = -1e9, sum = 0, from = 0, to = 0, f = 0;for (int i = 0; i < n; i ++ ){sum += num[i];if (sum > res) res = sum, from = f, to = i;if (sum < 0) sum = 0, f = i + 1;}if (res < 0) res = 0, from = 0, to = n - 1;cout << res << ' ' << num[from] << ' ' << num[to];return 0; }

• 思路 ：dp就是求很多集合中的最優(yōu)解。狀態(tài)表示為f[i]，集合是所有以i為右端點的區(qū)間，屬性是區(qū)間和的最大值，那么f[i]可以被分為兩個區(qū)間，一個是區(qū)間長度為1，那么區(qū)間和的最大值就是w[i]，一個是區(qū)間長度不為1，那么區(qū)間和的最大值就是f[i - 1] + w[i]，所以$f[i]=max(w[i],f[i?1]+w[i])$，也就是$f[i]=w[i]+max(0,f[i?1])$，由于這里f[i]只會用到f[i-1]，就發(fā)現(xiàn)其實f數(shù)組不需要開，可以用一個變量來存

#include <iostream>using namespace std;const int N = 1e4 + 10;int w[N];int main() {int n;cin >> n;for (int i = 1; i <= n; i ++ ) cin >> w[i];int res = -1, l, r;for (int i = 1, sum = -1, start; i <= n; i ++ ){if (sum < 0) sum = 0, start = i;sum += w[i];if (sum > res){res = sum;l = w[start], r = w[i];}}if (res < 0) res = 0, l = w[1], r = w[n];cout << res << ' ' << l << ' ' << r;return 0; }

1093 Count PAT’s (25 分)

題意 ：

• 字符串 APPAPT 中共包含兩個 PAT 作為子串。現(xiàn)在給定一個字符串，請你求出字符串中包含的 PAT 的數(shù)量。

思路 ：

• P的數(shù)量，PA的數(shù)量，PAT的數(shù)量
• dp問題中字符串下標從1開始
• 注意初始化f[0][0] = 1，因此！"0"不能用了，所以是f[n][3]表示答案，循環(huán)j層也要從0-3，p模式字符串也要加空格
• strlen在string.h頭文件中
  

#include <iostream> #include <string.h> using namespace std;const int N = 1e5 + 10, MOD = 1e9 + 7;int n; char s[N], p[] = " PAT"; int f[N][4];int main() {scanf("%s", s + 1);n = strlen(s + 1);f[0][0] = 1;for (int i = 1; i <= n; i ++ )for (int j = 0; j <= 3; j ++ ){f[i][j] = f[i - 1][j];if (s[i] == p[j]) f[i][j] = (f[i][j] + f[i - 1][j - 1]) % MOD;}printf("%d", f[n][3]); } #include <iostream> using namespace std;const int MOD = 1e9 + 7;int main() {string s; cin >> s;int n = s.size();int cntp = 0, cntpa = 0, cntpat = 0;for (int i = 0; i < n; i ++ ){if (s[i] == 'P') cntp ++ ;else if (s[i] == 'A') cntpa += cntp;else cntpat = (cntpat + cntpa) % MOD;}printf("%d", cntpat); }

1101 Quick Sort (25 分)

題意 ：

• 在著名的快速排序中，有一個經(jīng)典的過程叫做劃分。在此過程中，我們通常選取其中一個元素作為分界值。將小于分界值的元素移到其左側(cè)，將大于分界值的元素移到其右側(cè)。給定 N 個不同的正整數(shù)進行過一次劃分后的排列情況。請你判斷，共有多少元素可能是此次劃分的分界值。

思路 ：

• 用兩個數(shù)組表示i左邊的最大值和右邊的最小值；注意設(shè)置兩個哨兵

語法 ：

• 如果size為0，輸出v[0]會segment fault

#include <iostream> #include <vector>using namespace std;const int N = 100010, INF = 2e9;int n; int a[N], l[N], r[N];int main() {cin >> n;for (int i = 1; i <= n; i ++ ) cin >> a[i];for (int i = 1; i <= n; i ++ ) l[i] = max(l[i - 1], a[i]);r[n + 1] = INF;for (int i = n; i; i -- ) r[i] = min(r[i + 1], a[i]);vector<int> res;for (int i = 1; i <= n; i ++ )if (l[i - 1] < a[i] && a[i] < r[i + 1])res.push_back(a[i]);cout << res.size() << endl;if (res.size()){cout << res[0];for (int i = 1; i < res.size(); i ++ ) cout << ' ' << res[i];}cout << endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的PAT甲级题目翻译+答案 AcWing（动态规划）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。