dfs就可以了。加一个剪枝
1。如果这个人被捉弄后会回到编号小于当前编号的点那么这人在这点肯定被捉弄。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char use[110];
int x[110],y[110],t[110],SUM[110];
int best=0;
int KASE,n,f,totle=0;
void di(int k,int sum)
{
totle++;
if(totle>100000000)return;
if(k==n)
{
if(sum>best)best=sum;
return;
}
if(use[k])
{
use[k]=0;
if(k<t[k] && (SUM[t[k]]-SUM[k]+x[k]-x[t[k]]>y[k]));
else di(t[k],sum+y[k]);
use[k]=1;
}
if(use[k]&&t[k]<k);
else di(k+1,sum+x[k]);
}
int main()
{
int i;
srand(406);
scanf("%d",&KASE);
while(KASE--)
{
scanf("%d",&n);
memset(use,1,sizeof(use));
for(i=0;i<n;i++)
{
scanf("%d%d%d",&x[i],&y[i],&t[i]);
t[i]--;
}
SUM[0]=x[i];
for(i=1;i<n;i++)SUM[i]=SUM[i-1]+x[i];
best=0;
di(0,0);
printf("%d\n",best);
}
return 0;
}