作者:liu100897 | 来源:互联网 | 2023-09-17 23:02
code:
#include
#define N 1005
#define inf 0x3f3f3f3f
#define setIO(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
using namespace std;
int n;
int t[N],b[N],f[N][1<<10][20];
inline int Num(int x) { return x+8; }
inline void getmin(int &a,int b) { if(bvoid solve()
{
// setIO("candy");
int i,j,k,h;
scanf("%d",&n);
for(i=1;i<=n;++i) scanf("%d%d",&t[i],&b[i]);
memset(f,inf,sizeof(f));
f[1][0][Num(-1)]=0;
for(i=1;i<=n;++i)
{
for(j=0;j<(1<<8);++j)
{
for(k=-8;k<=7;++k)
if(f[i][j][Num(k)]!=inf)
{
if (j&1)
getmin(f[i+1][j>>1][Num(k-1)],f[i][j][Num(k)]);
else
{
int tmp=inf;
for (h=0;h<=7;++h)
if (!((j>>h)&1))
{
if(i+h>tmp) break;
getmin(tmp,i+h+b[i+h]);
getmin(f[i][j|(1< }
}
}
}
}
int res=inf;
for(i=0;i<=8;++i) res=min(res, f[n+1][0][i]);
printf("%d\n",res);
}
int main()
{
int T;
scanf("%d",&T);
while(T--) solve();
}