生日欢唱
题意
n个男，n个女排成两列。可以选择上来唱歌获得 $ a[i]*b[j]$ 的价值，否则若男 $or$ 女连续不上来损失 $(\sum a[i]) ^ 2$的价值。可以上来也可以不上来。求最大价值。
分析
显然是区间dp，考虑$f[i][j]$表示考虑前$i$个男生，前$j$个女生并且强制让$i,j$对唱最大价值。有转移如下。
不难考虑可以使一部分男生/女生不上来。则有 $f[i][j]=max(f[k][j-1]+a[i]*b[j]-\sum a[s])$
同理有女生。
最后强制令$n+1$价值都为0，强制匹配，答案为$f[n+1][n+1]$。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
const int N=310;
int a[N],suma[N],b[N],sumb[N];
int f[N][N];
signed main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
suma[i]=suma[i-1]+a[i];
}
for(int i=1;i<=n;i++){
scanf("%lld",&b[i]);
sumb[i]=sumb[i-1]+b[i];
}
suma[n+1]=suma[n],sumb[n+1]=sumb[n];
for(int i=1;i<=n;i++){
f[1][i]=a[1]*b[i]-(sumb[i-1]-sumb[0])*(sumb[i-1]-sumb[0]);
f[i][1]=a[i]*b[1]-(suma[i-1]-suma[0])*(suma[i-1]-suma[0]);
}
for(int i=2;i<=n+1;i++){
for(int j=2;j<=n+1;j++){
for(int k=1;k<i;k++){
f[i][j]=max(f[i][j],f[k][j-1]+a[i]*b[j]-(suma[i-1]-suma[k])*(suma[i-1]-suma[k]));
}
for(int k=1;k<j;k++){
f[i][j]=max(f[i][j],f[i-1][k]+a[i]*b[j]-(sumb[j-1]-sumb[k])*(sumb[j-1]-sumb[k]));
}
}
}
printf("%lld",f[n+1][n+1]);
return 0;
}
恐狼后卫
题意
有一个攻击值$atk$，攻击狼需要攻击至0血以下。耗费的代价是$a[i]+b[i-1]+b[i+1]*times$。求最小代价。
解法
$Notice$：注意消去时$cost=times[k]*(a[ k ]+ b[ l - 1 ] + b[ r + 1 ] ) $注意要想让它变为-血需要 $h[i]+atk-1$ 下取整
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e3+7;
int n,atk;
int a[N],b[N],h[N],times[N],f[N][N];
signed main(){
scanf("%lld%lld",&n,&atk);
cerr<<n<<" "<<atk<<" ";
for(int i=1;i<=n;i++){
scanf("%lld%lld%lld",&a[i],&b[i],&h[i]);
cerr<<a[i]<<" "<<b[i]<<" "<<h[i]<<" ";
// h[i]--;
}
for(int i=1;i<=n;i++){
int x=(int)ceil((h[i]+atk-1)/atk);//防止不小于0
// printf("需要%d次\n",x);
times[i]=x;f[i][i]=x*(a[i]+b[i+1]+b[i-1]);
}
for(int len=2;len<=n;len++){
for(int l=1;l+len-1<=n;l++){
int r=l+len-1;
f[l][r]=0x3f3f3f3f;
for(int k=l;k<=r;k++){
int cost=times[k]*(a[k]+b[l-1]+b[r+1]);
f[l][r]=min(f[l][r],f[l][k-1]+f[k+1][r]+cost);
}
}
}
printf("%lld",f[1][n]);
return 0;
}