题目大意:每个学生乘坐电梯如果不在自己想要停的楼层停下就会产生怒气值,在低于自己楼层停下,在停下的楼层就会产生一个怒气值,如果超过自己的楼层在上升的楼层,每一层都会产生一个怒气值,比如,想在5层楼停,电梯却在8楼停那么6,7两层都会产生怒气值,然后在8楼下电梯走到5楼。
状态转移方程:A(i)=minj<i A(j)+Pi−1 k=j(i−k)∗sk +Pn k=i sk (j is the previous stop)
#include<bits/stdc++.h>
using namespace std;
const int maxn=1500+10;
const int inf=1e9+7;
int anger[maxn],s[maxn];
int main()
{
freopen("in.txt","r",stdin);
int t;
int n;
scanf("%d",&t);
while(t--)
{
int sum=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&s[i]);
sum+=s[i];
}
anger[0]=0;//0层大家上电梯的那一层愤怒值为0;
for(int i=1;i<=n;i++)
{
sum-=s[i];//去往更高层的同学数量
int skipanger=0;
anger[i]=inf;
for(int j=i-1;j>=0;j--)
{
//int k=j;
anger[i]=min(anger[i],anger[j]+sum+skipanger);
skipanger+=(i-j)*s[j];//去往底层学生的愤怒值
}
}
cout<<anger[n]<<endl;
}
return 0;
}