后来我忍无可忍,因为每个DP状态的具体情况我都记录了下来
于是我开始扫描
use[t][t].A[i]
一旦其为true那么我就把这个药品的价值加上去。。
然后我就AC了
我郁闷啊。。。。我的f[t][t]到底是哪个地方错了啊!!!!
为什么会这样啊!!!
以下贴出我的
——————有问题却不知道问题在何处的程序
就是说f[t][t]的答案是错误的,大家帮忙看看——程序已经AC
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
const int CMAX = 501;
const int TMAX = 101;
struct note
{
long B;
long far;
long number;
long next;
};
struct note2 // 不要问我为什么变成结构体 结构体赋值的速度——位运算的速度,大家明白的
{
bool A[TMAX];
};
FILE *fp;
note way[TMAX];
note2 use[CMAX][CMAX];
long n,t,used,ans;
long f[CMAX][CMAX];
long money[TMAX];
long headway[CMAX];
void makeway(long a,long b,long c,long d)
{
used++;
money[d] = c;
way[used].next = headway[a];
way[used].B = b-1;
way[used].far = c;
way[used].number = d;
headway[a] = used;
}
void in()
{
fp=fopen("rqnoj99.in","r");
fscanf(fp,"%ld%ld",& t,& n);
for(long i=1;i<=n;i++)
{
long a,b,c;
fscanf(fp,"%ld%ld%ld",& a,& b,& c);
makeway(b,a,c,i);
}
fclose(fp);
}
void out()
{
fp=fopen("rqnoj99.out","w");
fprintf(fp,"%ld",ans);
fclose(fp);
}
void output()
{
fp=fopen("trying.out","w");
for(long i=1;i<=t;i++)
{
for(long j=1;j<=t;j++)
fprintf(fp,"%5ld",f[i][j]);
fprintf(fp,"\n");
}
for(long i=1;i<=n;i++)
fprintf(fp,"%2ld",use[t][t].A[i]);
fclose(fp);
}
int main()
{
in();
for(long i=0;i<=t;i++)
{
for(long j=0;j<=t;j++)
{
long ci = i , cj = j , add = 0 , chose = 0;
//output();
if(f[i-1][j] > f[i][j-1])
{
f[i][j] = f[i-1][j];
use[i][j] = use[i-1][j];
}
else
{
f[i][j] = f[i][j-1];
use[i][j] = use[i][j-1];
}
for(long k = headway[j];k!=0;k=way[k].next)
{
long B = way[k].B , far = way[k].far , number = way[k].number;
if(use[i][B].A[number]) continue;
if(f[i][B] + far <= f[ci][cj] + add) continue;
add = far;
ci = i;
cj = B;
chose = number;
}
for(long k = headway[i];k!=0;k=way[k].next)
{
long B = way[k].B , far = way[k].far , number = way[k].number;
if(use[B][j].A[number]) continue;
if(f[B][j] + far <= f[ci][cj] + add) continue;
add = far;
ci = B;
cj = j;
chose = number;
}
if(i == ci && j == cj) continue;
f[i][j] = f[ci][cj] + add;
use[i][j] = use[ci][cj];
use[i][j].A[chose] = true;
}
}
//output();
for(long i=1;i<=n;i++)
if(use[t][t].A[i] == true)
ans += money[i];
out();
return 0;
}