头一回自己写出来个这么难的动规，小小的激动一下。。
如果直接把100分的代码贴出来，也没啥用。我把分数逐渐增长的所有代码都贴出来，万一自己以后又做到这道题没有思路可作参考。
确实很麻烦。如果直接看100分的会一头雾水，还写不出来注释，思想太复杂了。只可意会。
想看简单题解的OIer可以去洛谷题解上看。
63分：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | #include<iostream> #include<cstring> #include<algorithm> #define ll long long #define pii pair<int,int> #define PINF 0x7fffffff #define NINF 0x80000000 using namespace std; int n; int price[5005]; int dp[5005]; int ways[5005]; bool visited[65537]; int main() { cin >> n; for (int i = 1; i <= n; i++)cin >> price[i]; for (int i = 1; i <= n+1; i++) { int mDpV = 0, cWays = 1; for (int j = 1; j < i; j++) { if (price[j] > price[i]) { if (dp[j] > mDpV) { mDpV = dp[j]; cWays = ways[j]; memset(visited, false, sizeof(visited)); visited[price[j]] = true; } if (dp[j] == mDpV && !visited[price[j]]) { cWays += ways[j]; visited[price[j]] = true; } } } dp[i] = mDpV + 1; ways[i] = cWays; } cout << dp[n+1]-1 << " " <<ways[n+1]; } |
73分：把memset的范围调小了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | #include<iostream> #include<string> #include<cstring> #include<algorithm> #include<queue> #define ll long long #define pii pair<int,int> #define PINF 0x7fffffff #define NINF 0x80000000 using namespace std; int n; int price[5005]; int dp[5005]; int ways[5005]; bool visited[65537]; int main() { cin >> n; price[0] = 65537; ways[0] = 1; int vmax = 0, vmin = 65537; for (int i = 1; i <= n; i++) { cin >> price[i]; vmax = max(vmax, price[i]); vmin = min(vmin, price[i]); } for (int i = 1; i <= n+1; i++) { int mDpV = dp[0], cWays = 1; for (int j = 1; j < i; j++) { if (price[j] > price[i]) { if (dp[j] > mDpV) { mDpV = dp[j]; cWays = ways[j]; memset(visited + vmin, false, sizeof(int)*(vmax - vmin + 1)); visited[price[j]] = true; } if (dp[j] == mDpV && !visited[price[j]]) { cWays += ways[j]; visited[price[j]] = true; } } } dp[i] = mDpV + 1; ways[i] = cWays; } cout << dp[n+1]-1 << " " <<ways[n+1]; } |
82分：不在每个j处都memset，而是利用版本号的想法，改为在i处更新。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | #include<iostream> #include<cstring> #include<algorithm> #define ll long long #define pii pair<int,int> #define PINF 0x7fffffff #define NINF 0x80000000 using namespace std; int n; int price[10000]; long long dp[10000]; long long ways[10000]; int visited[65540]; //[price][version()] int main() { cin >> n; int vmax = 0, vmin = 65537; for (int i = 1; i <= n; i++) { cin >> price[i]; vmax = max(vmax, price[i]); vmin = min(vmin, price[i]); } for (int i = 1; i <= n+1; i++) { long long mDpV = 0; long long cWays = 1; memset(visited, 0, sizeof(visited)); for (int j = 1; j < i; j++) { if (price[j] > price[i]) { if (dp[j] > mDpV) { mDpV = dp[j]; cWays = ways[j]; visited[price[j]] = mDpV; } if (dp[j] == mDpV && visited[price[j]]<mDpV) { cWays += ways[j]; visited[price[j]] = mDpV; } } } dp[i] = mDpV + 1; ways[i] = cWays; } cout << dp[n+1]-1 << " " <<ways[n+1]; } |
100分：参考别人题解发现了用后面替代前面的重要问题。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | #include<iostream> #include<cstring> #include<algorithm> #define ll long long #define pii pair<int,int> #define PINF 0x7fffffff #define NINF 0x80000000 using namespace std; int n; int price[10000]; long long dp[10000]; //DP 数组 long long ways[10000]; //方法数 数组 long long visited[65540][2]; // [price][0]代表当前最长降序子序列长度，[price][1]代表在此情况下的方法数 int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> price[i]; for (int i = 1; i <= n+1; i++) { long long mDpV = 0; long long cWays = 1; memset(visited, 0, sizeof(visited)); for (int j = 1; j < i; j++) { if (price[j] > price[i]) { //当visited[price[j]][0]有更新时，用后面的替代前面的，因为相应的方法数也会有更新 if (dp[j] == mDpV && visited[price[j]][0]==mDpV) { cWays += ways[j]; cWays -= visited[price[j]][1]; visited[price[j]][1] = ways[j]; } else if (dp[j] == mDpV && visited[price[j]][0]<mDpV) { cWays += ways[j]; visited[price[j]][0] = mDpV; visited[price[j]][1] = ways[j]; } else if (dp[j] > mDpV) { mDpV = dp[j]; cWays = ways[j]; visited[price[j]][0] = mDpV; visited[price[j]][1] = ways[j]; } } } dp[i] = mDpV + 1; ways[i] = cWays; } cout << dp[n+1]-1 << " " <<ways[n+1]; } |