简单的网站代码,wordpress代码修改,免费的html5模板,大专软件技术好学吗文章目录题目描述解析代码thanks for reading#xff01;题目描述 解析
这题挺好的 思路#xff1a;dp[i][j]表示必须把i和j配对#xff0c;可达到的最大值 首先#xff1a;
dp[i][j]dp[i-1][j-1]a[i]*b[j];然后可以分别尝试把男生或女生往前放弃一段#xff1a;
for(i…
文章目录题目描述解析代码thanks for reading题目描述 解析
这题挺好的 思路dp[i][j]表示必须把i和j配对可达到的最大值 首先
dp[i][j]dp[i-1][j-1]a[i]*b[j];然后可以分别尝试把男生或女生往前放弃一段
for(int ki-1;k1;k--){//男不要k到i-1 dp[i][j]max(dp[i][j],dp[k-1][j-1]a[i]*b[j]-(suma[i-1]-suma[k-1])*(suma[i-1]-suma[k-1]));}for(int kj-1;k1;k--){//女不要k到j-1 dp[i][j]max(dp[i][j],dp[i-1][k-1]a[i]*b[j]-(sumb[j-1]-sumb[k-1])*(sumb[j-1]-sumb[k-1]));}这道题我看了题解 我本来也有类似的想法但当时我觉得男生女生可能都放弃了一段所以应该同时枚举男生和女生放弃的位置这样时间复杂度就变成了n^4无法接受 但是我忽略了一个性质ab都不小于0所以两边都放弃肯定不如让放弃的那两段再配对一些好所以每次一定只会放弃一边 这样就变成了题解的n^3思路
另外本题还有一些有意思的细节 1.再后面再加上一对水平为0的男女最后统计dp[n1][n1]这样就可以包含那些没有取到第n对的正解 2.i不等于0时dp[0][i]和dp[i][0]都是没有意义的所以应该赋值为无穷小 3.虽然答案在int范围内但前缀和之差平方的操作会爆int所以应该开longlong 代码
#includebits/stdc.h
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N600;
const int M2e6100;
int m,n;
ll dp[N][N];
ll a[N],b[N],suma[N],sumb[N];
int main(){scanf(%d,n);for(int i1;in;i){scanf(%d,a[i]);suma[i]suma[i-1]a[i];
// printf(i%d sum%d\n,i,suma[i]);}for(int i1;in;i){scanf(%d,b[i]);sumb[i]sumb[i-1]b[i];}a[n]0;b[n]0;suma[n]suma[n-1];sumb[n]sumb[n-1];//再加一对for(int i0;in;i){for(int j0;jn;j) dp[i][j]-2e9;}dp[0][0]0;for(int i1;in;i){for(int j1;jn;j){dp[i][j]dp[i-1][j-1]a[i]*b[j];for(int ki-1;k1;k--){//不要k到i-1
// printf(aa\n);dp[i][j]max(dp[i][j],dp[k-1][j-1]a[i]*b[j]-(suma[i-1]-suma[k-1])*(suma[i-1]-suma[k-1]));}for(int kj-1;k1;k--){//不要k到j-1
// printf(bb\n);dp[i][j]max(dp[i][j],dp[i-1][k-1]a[i]*b[j]-(sumb[j-1]-sumb[k-1])*(sumb[j-1]-sumb[k-1]));}
// printf(i%d j%d dp%d\n,i,j,dp[i][j]);}} printf(%lld,dp[n][n]);return 0;
}
thanks for reading
