洛谷1854花屋のショーウインドーの配置
935 ワード
dp水題では、i番目の花は少なくともi番目の花瓶に入れなければならないことに気づいたので、どの花瓶に置くかを列挙しました.
この花はここに置くと置かないとmaxを取ります
f[i][k]=max(f[i][k],f[i-1][j-1]+c[i][k])
コード#コード#
この花はここに置くと置かないとmaxを取ります
f[i][k]=max(f[i][k],f[i-1][j-1]+c[i][k])
コード#コード#
//By AcerMo
#include
#include
#include
#include
#include
using namespace std;
const int M=-10000000;
int n,m,qlm;
int c[200][200],f[120][120];
void coutt(int x,int y)
{
if (x>0)
{
int qlm=x;
while (f[x][qlm]!=y) qlm++;
coutt(x-1,y-c[x][qlm]);
printf("%d ",qlm);
}
return ;
}
int main()
{
cin>>n>>m;int ans=0;
for (int i=1;i<=n;i++)
for (int k=1;k<=m;k++)
scanf("%d",&c[i][k]),f[i][k]=M;
for (int i=1;i<=n;i++)
for (int k=i;k<=m;k++)
for (int j=i-1;j