窈窕淑女

窈窕淑女

Description

　　“关关雎鸠，在河之洲。窈窕淑女，君子好逑。”——《诗经》
　　T博士的大儿子阿T（阿嚏？）最近遇到了一件麻烦事。
　　有n个MM同时邀请阿T在8月14日上午11:30拜访她们家，可那时阿T刚比赛完，所以不能先提前拜访几个，而他又不会分身术，所以他只得分别拜访。他共有T分钟的时间可以用于拜访MM。他还安排好了拜访的顺序，对于每个MM都可以选择拜访或不拜访。对于要拜访的MM必须按阿T安排好的顺序拜访。
　　对于每个MM都有如下数据：
　　不高兴系数x，为2到9的整数。
　　不高兴度X，若阿T迟到t分钟到她家，则X=x^t（x的t次方）；若阿T不拜访她家，则X=x^T。
拜访时间y（分钟），保证0

The Solution

一道dp（跌屁）题。我们可以设 f[i][j]代表前i个人，用了j的时间，所达到的最小值。

正推

f[i+1][j]=min(f[i+1][j],f[i][j]+x[i+1]t) $$f[i + 1][j] = min(f[i + 1][j],f[i][j] + x[i + 1] ^ t)$$ 不取i + 1这个人。

f[i+1][j+y[i+1]]=min(f[i+1][j+y[i+1]],f[i][j]+x[i+1]j) $$f[i + 1][j + y[i + 1]] = min(f[i + 1][j + y[i + 1]],f[i][j] + x[i + 1] ^ j)$$
取走i这个人。

结果在所有的f[n][i]中取最小。

结果绝对很大，样例都这样了。。。
所以机智的我们要用高精度。。
又是第一次用c++打了返回值为数组的高精度。（好像说的不是很准确。。不管了）

用struct的
dp高精度也是第一次打啊，打得有点猥琐，不要见怪。。

#define HownoneHe
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#define fo(i,a,b) for (int i=a;i<=b;i++)
#define fd(i,a,b) for (int i=a;i>=b;i--)
#define N 25
#define T 200
#define ya 100000
#define MAXN 21
#define MAXT 190
#define BASE 10000
using namespace std;
struct note
{int x[100];
}F[N][T],Mi[10][T],ans;
int n,t;
int a[N],b[N];note Min(note a,note b)
{if (a.x[0]==-1) return b;if (b.x[0]==-1) return a;if (a.x[0]<b.x[0]) return a;if (a.x[0]>b.x[0]) return b;fd(i,a.x[0],1) {if (a.x[i]<b.x[i]) return a;if (a.x[i]>b.x[i]) return b;}return a;
}note jia(note a,note b)
{note c;memset(c.x,0,sizeof(c.x));c.x[0]=max(a.x[0],b.x[0]);fo(i,1,c.x[0]){c.x[i]+=a.x[i]+b.x[i];c.x[i+1]+=c.x[i]/ya;c.x[i]%=ya;}if (c.x[c.x[0]+1]) c.x[0]++;return c;
}
note cheng(note a,int b)
{note c;memset(c.x,0,sizeof(c.x));c.x[0]=a.x[0];fo(i,1,c.x[0]){c.x[i]+=a.x[i]*b;c.x[i+1]+=c.x[i]/ya;c.x[i]%=ya;}if (c.x[c.x[0]+1]) c.x[0]++;return  c;
}
int main()
{scanf("%d%d",&n,&t);fo(i,1,n) scanf("%d%d",&a[i],&b[i]);fo(i,2,9) Mi[i][0].x[0]=Mi[i][0].x[1]=1;fo(i,2,9)fo(j,1,t) Mi[i][j]=cheng(Mi[i][j-1],i);fo(i,0,n) fo(j,0,t) F[i][j].x[0]=-1;F[0][0].x[0]=1;fo(i,0,n-1) fo(j,0,t)if (F[i][j].x[0]!=-1){F[i+1][j]=Min(F[i+1][j],jia(F[i][j],Mi[a[i+1]][t]));if (j+b[i+1]<=t)F[i+1][j+b[i+1]]=Min(F[i+1][j+b[i+1]],jia(F[i][j],Mi[a[i+1]][j]));}ans.x[0]=-1;fo(i,0,t) if (F[n][i].x[0]!=-1) ans=Min(ans,F[n][i]);   printf("%d",ans.x[ans.x[0]]);fd(i,ans.x[0]-1,1) printf("%05d",ans.x[i]);return 0;
}