HDU 2078 复习功课（记忆化搜索）

水深无声 2024-02-17 19:42 31阅读 0赞

为了能过个好年，xhd开始复习了，于是每天晚上背着书往教室跑。xhd复习有个习惯，在复习完一门课后，他总是挑一门更简单的课进行复习，而他复习这门课的效率为两门课的难度差的平方,而复习第一门课的效率为100和这门课的难度差的平方。xhd这学期选了n门课，但是一晚上他最多只能复习m门课，请问他一晚上复习的最高效率值是多少？

Input

输入数据的第一行是一个数据T，表示有T组数据。  
每组数据的第一行是两个整数n(1 <= n <= 40)，m(1 <= m <= n)。  
接着有n行，每行有一个正整数a(1 <= a <= 100)，表示这门课的难度值。

Output

对于每组输入数据，输出一个整数，表示最高效率值。

Sample Input

2
    2 2
    52
    25
    12 5
    89
    64
    6
    43
    56
    72
    92
    23
    20
    22
    37
    31

Sample Output

5625
    8836

网上看了很多用的比较简单的数学方法（只复习一门最简单的功课），当时没想到这个方法，就写了一波记忆化搜索……

AC代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn=40+3;
    int a[maxn];
    int d[maxn];
    int n,m;
    bool cmp(int a,int b){
    	return a>b;
    }
    int dp(int i,int m1,int tol){ //i表示当前搜索位置，m1表示要复习多少功课，tol表示最多能复习的功课数 
    	int&ans =d[i];
    	if(ans>0)return ans;
    	if(m1>tol)return 0;
    	
    	for(int j=i+1;j<=n;j++){
    		ans=max(ans,dp(j,m1+1,tol)+(a[i]-a[j])*(a[i]-a[j]));
    	}
    	return ans;
    }
    int main(){
    	int T;
    	scanf("%d",&T);
    	while(T--){
    		scanf("%d%d",&n,&m);
    		for(int i=1;i<=n;i++)
    		scanf("%d",&a[i]);
    		a[0]=100;
    		memset(d,0,sizeof(d));
    		sort(a,a+n+1,cmp);  //大到小排序 
    		
    		int ans=0;
    		for(int i=1;i<=m;i++){
    			ans=max(ans,dp(0,1,i));
    		}
    		printf("%d\n",ans);
    	}
    	return 0;
    }