dfs就可以了。加一個(gè)剪枝
1。如果這個(gè)人被捉弄后會回到編號小于當(dāng)前編號的點(diǎn)那么這人在這點(diǎn)肯定被捉弄。
#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;
}