Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## DP 900MS险过。。附代码

Posted by yzhw at 2011-04-02 11:15:48 on Problem 1907
```# include <cstdio>
# include <cstdlib>
# include <cstring>
# include <algorithm>
using namespace std;
struct node
{
char name[20];
int num,a,b;
bool operator<(const node &pos) const
{
if(num!=pos.num) return num<pos.num;
else return strcmp(name,pos.name)<0;
}
}res[105];
int dp[100005];
int main()
{
int testcase;
scanf("%d",&testcase);
for(int test=1;test<=testcase;test++)
{
int n,m,num;
scanf("%d%d%d",&n,&m,&num);
for(int i=0;i<num;i++)
{
char str[50];
scanf("%s",str);
strcpy(res[i].name,strtok(str,":"));
res[i].a=atoi(strtok(NULL,","));
res[i].b=atoi(strtok(NULL," "));
memset(dp,-1,sizeof(dp));
dp[n]=0;
for(int j=n;j>=m;j--)
if(dp[j]!=-1)
{
if(j/2>=m&&(dp[j/2]==-1||dp[j/2]>dp[j]+res[i].b))
dp[j/2]=dp[j]+res[i].b;
if(j-1>=m&&(dp[j-1]==-1||dp[j-1]>dp[j]+res[i].a))
dp[j-1]=dp[j]+res[i].a;
}
res[i].num=dp[m];
}
sort(res,res+num);
printf("Case %d\n",test);
for(int i=0;i<num;i++)
printf("%s %d\n",res[i].name,res[i].num);
}
return 0;
}
```

Followed by: