DP问题
#include<iostream>
#include<fstream>
using namespace std;
long a[13];
long f[13][1000];
int main()
{
ifstream cin("a.txt");
long c1,c2,c3,i,j,k;
long n,max,min;
while(cin>>n)
{
if(n==0) break;
cin>>c1>>c2>>c3;
/*cout<<c1<<c2<<c3; 输入第二行值*/
max=0;
for(i=1;i<=n;i++)
{
cin>>a[i];//第i个月需要的员工数
if(a[i]>max) max=a[i];//确定最大员工数
}
for(i=a[1];i<=max;i++)//第一个月员工增加到max 分别对应的花费
{
f[1][i]=(c1+c2)*i;//c1:雇佣费用 c2 工资
}
for(i=2;i<=n;i++)//第二个月开始循环
{
for(j=a[i];j<=max;j++)//第i个月员工增加到max
{
f[i][j]=0x7FFFFFFF;//?
for(k=a[i-1];k<=max;k++)//第i-1个月员工增加到max
{
if(j<k)//j,k表示员工数
{
if(f[i-1][k]+c3*(k-j)+j*c2<f[i][j])//i-1月与i月比较,i月变成j人
f[i][j]=f[i-1][k]+c3*(k-j)+j*c2;//?
}
else if(j==k)
{
if(f[i-1][k]+c2*j<f[i][j])
f[i][j]=f[i-1][k]+c2*j;
}
else if(j>k)
{
if(f[i-1][k]+c1*(j-k)+c2*j<f[i][j])
f[i][j]=f[i-1][k]+c1*(j-k)+c2*j;
}
}
}
}
min=f[n][a[n]];//?
for(i=a[n]+1;i<=max;i++)
if(f[n][i]<min) min=f[n][i];
cout<<min<<endl;
}
return 0;
}
这个dp问题有些地方看不懂 ,哪位大侠给解释一下(最好详尽点,小弟菜鸟)!!
[解决办法]
帮顶~
[解决办法]
请教DP是what？
[解决办法]
对了，LZ 最好把问题描述一下，这样才好知道这个程序是做什么的，才好知道DP的状态转移方程啊
[解决办法]
文件内容不清楚~
不好理解~
[解决办法]
因为懒,我才用编程简化生活!
那么。。你得勤快点。。。^_^
[解决办法]
楼主貌似你没说哪个地方不懂...
不过所有的问题在理解的时候始终要记住自己要解决的到底是什么，不然容易转晕的~
好久没来论坛了，貌似是开年后几个月来第一次回帖咯~哈哈，堕落了简直
