有n个苹果，和一个数k，第i个苹果的重量是k+i(1<=i<=n). 已知其中只有一个苹果是甜的，所有比它重量轻的都是苦的，比它重的都是酸的。为了要找出甜的苹果，就要去一个一个地吃它，且吃了咬了苹果就必须把它吃完，不管苹果是苦的还是酸的。
例如，先吃#1,
如果#1是甜的，花费1
如果#2是甜的，那么选择吃#3，不管#3是什么味道，都可以推测出#2和#4的味道，那么花费1+3
如果#3是甜的，第二次选择吃#3, 共花费1+3 = 4
如果#5是甜的，方案和上面一样, 共花费1+3 = 4
总共1+4+4+4 = 13，这方案更好。
给出n和k，问最少的吃的苹果总重量是多少？
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N= 503 ;
int n,m,f[N][N];
int dp(int l,int r){
if(l>r) return 0;
if(f[l][r]!=-1) return f[l][r];
if(l==r ) return f[l][r];
int t= 1e9;
for(int k=l;k<=r;k++)
t=min(t,dp()+f[k+1][r]+(k+m)*(r-l+1));
return f[l][r] =t;
}
signed main(){
int tes;cin>>tes;
int cas=0;
while(tes--){
cin>>n>>m;
memset(f,-1,sizeof f) ;
printf("Case %d: %d\n", ++cas,dp(1, n));
}
}