HDU 2955

思路

这道题唯一要注意的是概率的连乘，不是加法！！！
我记录的是每个不被抓住的概率。那么，用dp[i]表示偷了i元钱不被抓住的概率。
用膝盖可以推得一下转移方程：

dp[j]=max(dp[j],dp[j-bk[i].money]*bk[i].risk);

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>  
#include <cstdio>
#include <math.h>
#include <cstring>
#include <algorithm>
using namespace std;
#define inf 0x3f3f3f3f  
const int MAXN=100005;
struct  bank
{
    int money;
    double risk;
}bk[105];
double dp[11000];
int main(){
    int t;
   for(cin>>t;t;t--){
     double maxrisk;int n,sum=0;
     cin>>maxrisk>>n;
     for(int i=1;i<=n;i++){
        scanf("%d%lf",&bk[i].money,&bk[i].risk);
        sum+=bk[i].money;bk[i].risk=1-bk[i].risk;
     }
     memset(dp,0,sizeof(dp));dp[0]=1;
     for(int i=1;i<=n;i++){
        for(int j=sum;j>=bk[i].money;j--){
            dp[j]=max(dp[j],dp[j-bk[i].money]*bk[i].risk);
        }
     }
     int cnt=sum;
     while((1-dp[cnt])>maxrisk && cnt>=0 ){
        cnt--;
     }
     cout<<cnt<<endl;
   }
    return 0;
}

HDU 1520

思路

最简单的树状dp，dp[i][0/1]表示第i个点取或者不取得最大值。
用手指甲可以推出这个转移方程。

dp[root][1]+=dp[u][0];
dp[root][0]+=max(dp[u][1],dp[u][0]);

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <cstring>
#include <stdio.h>
using namespace std;
const int NV=6005;
int head[NV];
int value[NV];
int n,cnt=0;
int dp[NV][2];
bool inv[NV];
struct  edge
{
	int to,next;
}E[NV*2];
void add(int a,int b){
	E[++cnt].to=b;
	E[cnt].next=head[a];
	head[a]=cnt;
}
void dfs(int root){
	dp[root][0]=0;
	dp[root][1]=value[root];
	for(int i=head[root];i!=-1;i=E[i].next){
		int u=E[i].to;
		dfs(u);
		dp[root][1]+=dp[u][0];
		dp[root][0]+=max(dp[u][1],dp[u][0]);
	}
	return ;
}
int main(){
	while(cin>>n){
		cnt=0;
		for(int i=1;i<=n;i++){
			scanf("%d",&value[i]);
			inv[i]=0;head[i]=-1;
		}
		int a,b;
		while(scanf("%d%d",&a,&b)){
			if(a==0&&b==0)break;
			add(b,a);
			inv[a]=1;
		}
		int root=0;
		for(int i=1;i<=n;i++){
			if(!inv[i]){
				root=i;break;
			}
		}	
		dfs(root);
		printf("%d\n",max(dp[root][0],dp[root][1]));
	}
	return 0;
}

HDU 2089

思路

数位dp，代码可观

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
using namespace std;
int dp[8][10],l,r,dig[10];
void init(){
	dp[0][0] = 1;
	for(int i = 1 ; i <=7 ; i++)
		for(int j = 0 ; j < 10 ; j++)
			for(int k = 0 ; k < 10 ; k++)
				if( j != 4 && !(j==6 && k==2))
					dp[i][j] += dp[i-1][k];
}
int work(int x){
	int cnt=0;
	while(x){
		dig[++cnt]=x%10;
		x/=10;
	}
	int ans=0;dig[cnt+1]=0;
	for(int i = cnt ; i >=1 ; i--){
		for(int j = 0; j < dig[i] ; j++)
			if(j != 4 && !(j==2 && dig[i+1]==6))
				ans += dp[i][j];
		if(dig[i]==4 || (dig[i]==2 && dig[i+1]==6))
			break;
	}
	return ans;
}
int main(){
	init();
	while(cin>>l>>r){
		if(l+r ==0)break;
		else cout<<work(r+1)-work(l)<<endl;
	}
	return 0;
}