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;
}