从同学那里看到的,如果把二维数组改成多个一维数组,时间效率会高很多。
不知道是不是,反正我就用了
#include <iostream>
using std::cout;
using std::cin;
struct cost
{
long num;
long tim;
void operator>?=(cost);
cost operator+(cost);
//void operator=(long);
};
void cost::operator>?=(cost c2)
{
if (c2.num>num)
{
num = c2.num;
tim = c2.tim;
}
else if (c2.num==num)
{
tim <?= c2.tim;
}
}
cost cost::operator+(cost c2)
{
cost tmp;
tmp.num = num+c2.num;
tmp.tim = tim+c2.tim;
return tmp;
}
// t m r
cost f1[102][102];
cost f2[102][102];
long tim[102];
long rmb[102];
long rp [102];
long least[102];
long n;long m;long r;
int main()
{
cin >> n;
for (long i=1;i<n+1;i++)
{
cin >> rmb[i] >> rp[i] >> tim[i];
}
cin >> m >> r;
for (long i=1;i<n+1;i++)
{
for (long j=1;j<m+1;j++)
{
for (long k=1;k<r+1;k++)
{
if (i%2==1)
{
f1[j][k]>?=f2[j][k];
cost tmp;
tmp.num = 1;
tmp.tim = tim[i];
if (j-rmb[i]>=0&&k-rp[i]>=0)
f1[j][k]>?=f2[j-rmb[i]][k-rp[i]]+tmp;
}
else
{
f2[j][k]>?=f1[j][k];
cost tmp;
tmp.num = 1;
tmp.tim = tim[i];
if (j-rmb[i]>0&&k-rp[i]>=0)
f2[j][k]>?=f1[j-rmb[i]][k-rp[i]]+tmp;
}
}
}
}
cost max;
max.tim = 0x7fff0000;
max.num = 0;
for (long j=1;j<=m;j++)
{
for (long k=1;k<=r;k++)
{
if (n%2 == 1)
max >?= f1[j][k];
else
max >?= f2[j][k];
}
}
cout << max.tim;
//cout << least;
}