简单的01背包，直接做有点麻烦，可以转化为在大于逃脱率的情况下可以获得的最大钱数也就是求得到某个钱数时的最大逃脱率，状态转移方程是 dp[j]=max(dp[j],dp[j-s[i].m]*s[i].p)

初值dp[0]=1 ,因为不偷钱当然是不被抓的，这里的dp[j]就是获得j钱数可以达到的最大逃脱率！几次抢劫必须同时逃脱才可以，因此概率要乘！这里有个常数级的优化，可以用sum[i] 记录前i的银行（包括i）的钱数和，这样第二个循环就可以是for(j = sum[i] ; j>=s[i].m;j--) , 因为当j >sum[i] 时 j-s[i].m>sum[i-1] (sum[i]-sum[i-1]=s[i].m)这时的dp[j-s[i].m]显然还没有算出来，因为此时最多只算到了sum[i-1] !

#include<iostream>
#include<math.h>
#define M 105
using namespace std;

struct ss {
    double p;
    int m;
} s[M];

int main() {
    int t, i, j, n, sum[M];
    double dp[M * M], P;
    scanf("%d", &t);
    while (t-- && scanf("%lf %d", &P, &n)) {
        P = 1 - P;
        memset(dp, 0, sizeof (dp));
        dp[0] = 1;
        sum[0] = 0;
        for (i = 1; i <= n; i++) {
            scanf("%d %lf", &s[i].m, &s[i].p);
            s[i].p = 1 - s[i].p;
            sum[i] = sum[i - 1] + s[i].m;
        }
        for (i = 1; i <= n; i++)
            for (j = sum[n]; j >= s[i].m; j--)
                dp[j] = max(dp[j], dp[j - s[i].m] * s[i].p);
        for (j = sum[n]; j >= 1; j--)
            if (dp[j] > P)break;
        printf("%d\n", j);
    }
    return 0;
}

已知一多边形没有边相交，质量分布均匀。顺序给出多边形的顶点坐标，求其重心。

分析：

求多边形重心的题目大致有这么几种：

1，质量集中在顶点上。n个顶点坐标为(xi,yi)，质量为mi，则重心
　　X = ∑( xi×mi ) / ∑mi
　　Y = ∑( yi×mi ) / ∑mi
　　特殊地，若每个点的质量相同，则
　　X = ∑xi / n
　　Y = ∑yi / n

2，质量分布均匀。这个题就是这一类型，算法和上面的不同。
　　特殊地，质量均匀的三角形重心：
　　X = ( x0 + x1 + x2 ) / 3
　　Y = ( y0 + y1 + y2 ) / 3

3，质量分布不均匀。只能用积分来算，不会……

下面讨论这个题的解法：

以第一个顶点为基准，分别连接p[i]，p[i+1]，1<i<n。将多边形划分为若干个三角形。

若我们求出了每个三角形的重心和质量，可以构造一个新的多边形，顶点为所有三角形的重心，顶点质量为三角形的质量。这个新多边形的质量和重心与原多边形相同，即可使用第一种类型的公式计算出整个多边形的重心。

由于三角形的面积与质量成正比，所以我们这里用面积代替质量来计算。

现在有个问题就是，多边形有可能为凹多边形，三角形有可能在多边形之外。如何处理这种情况呢？

很简单，我们使用叉积来计算三角形面积，当三角形在多边形之外时，得到“负面积”就抵消掉了。
S =( x0*y1 + x1*y2 + x2*y0
- x1*y0 - x2*y1 - x0*y2 ) /2;

模版程序

# include<iostream>
# include<algorithm>
using namespace std;
const int maxNum = 1000000 +2;

struct point
{
double x, y;
};
struct point data[maxNum];

struct point bcenter(struct point pnt[], int n)【可以用来做模板】
{
point p, s;
double tp, area = 0, tpx = 0, tpy = 0;

p.x = pnt[0].x; p.y = pnt[0].y;

for (int i = 1; i <= n; ++i)
{

s.x = pnt[(i == n) ? 0 : i].x;
s.y = pnt[(i == n) ? 0 : i].y;
tp = (p.x * s.y - s.x * p.y);
area += tp / 2;
tpx += (p.x + s.x) * tp;
tpy += (p.y + s.y) * tp;
p.x = s.x;
p.y = s.y;
}
s.x = tpx / (6 * area);
s.y = tpy / (6 * area);
return s;
}
//OR:

This source is shared by zyd150

#include<stdio.h>
#include<math.h>
#define MAX 1000001
struct point{
    double x,y;
};
int n;
struct point p[MAX],v,ans;
void process(){
    int i,j,k;
    double s,ss=0;
    ans.x=ans.y=0;
    for(i=0;i<n;i++){
        j=(i+1)%n;
        v.x=(p[i].x+p[j].x)/3.0;
        v.y=(p[i].y+p[j].y)/3.0;
        s=(p[i].x*p[j].y-p[i].y*p[j].x)/2.0;
        v.x*=s;v.y*=s;ss+=s;
        ans.x+=v.x;ans.y+=v.y;
    }
    ans.x/=ss;ans.y/=ss;
    if(fabs(ans.x)<0.000001) ans.x=0;
    if(fabs(ans.y)<0.000001) ans.y=0;
    printf("%.2lf %.2lf\n",ans.x,ans.y);
}
int main(){
    int cas,i;
    scanf("%d",&cas);
    while(cas--){
        scanf("%d",&n);
        for(i=0;i<n;i++)
            scanf("%lf%lf",&p[i].x,&p[i].y);
        process();
    }
    return 0;
}

#include<stdio.h>
#include<math.h>
#define MAX 1000001
struct point{
	double x,y;
};
int n;
struct point p[MAX],v,ans;
void process(){
	int i,j,k;
	double s,ss=0;
	ans.x=ans.y=0;
	for(i=0;i<n;i++){
		j=(i+1)%n;
		v.x=(p[i].x+p[j].x)/3.0;
		v.y=(p[i].y+p[j].y)/3.0;
		s=(p[i].x*p[j].y-p[i].y*p[j].x)/2.0;
		v.x*=s;v.y*=s;ss+=s;
		ans.x+=v.x;ans.y+=v.y;
	}
	ans.x/=ss;ans.y/=ss;
	if(fabs(ans.x)<0.000001) ans.x=0;
	if(fabs(ans.y)<0.000001) ans.y=0;
	printf("%.2lf %.2lf\n",ans.x,ans.y);
}
int main(){
	int cas,i;
	scanf("%d",&cas);
	while(cas--){
		scanf("%d",&n);
		for(i=0;i<n;i++)
			scanf("%lf%lf",&p[i].x,&p[i].y);
		process();
	}
	return 0;
}

int main()
{

int T,i,j,num;
struct point re;
scanf("%d",&T);
while(T--)
{
scanf("%d",&num);
for(i = 0; i < num ; i ++)
scanf("%lf %lf",&data[i].x,&data[i].y);

re = bcenter(data,num);
printf("%.2lf %.2lf\n",re.x,re.y);
}
return 0;
}

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<algorithm>
#include<iomanip>
using namespace std;
int main()
{
    int T,count=1;
    cin>>T;
    while(T--)
    {
        int n,k;
        cin>>n>>k;
        cout<<"Case "<<count++<<": ";
        if((n&1&&k==1)||k>=n)
            cout<<"first"<<endl;
        else
            cout<<"second"<<endl;
    }
    return 0;
}

//cankao others
本题类似我曾今玩过的的一个NDS解密游戏《雷顿教授与魔神之笛》里的一道谜题。游戏里是给你15个围成圈的水龙头，开始它们全都是打开漏水的。接着你要跟电脑博弈，从电脑开始，双方可以选择关闭连续的两个水龙头（当然，已关的不能再打开了）也可以只选择关掉一个，最终没水龙头可关的将失败。在没学相关知识之前那迷题一直让我挺头疼的。。。

那个游戏的答案解法是，由于电脑一定会先关掉两个水龙头，接着你只要关掉剩余水龙头的中间那个，因而将剩余的水龙头分成数目相等的两个部分。那后无论电脑操作哪一部分的一或二个水龙头，你只要一样对称地关掉另一部分得水龙头。那你一定会是胜利者！

本题相当于是该迷题的一个拓展。

我们首先要分几种情况考虑：

1.当  K=1时，若N为奇数，则first wins，N为偶数则second wins。

2.当  K>=N时，first wins。

3.当  N>K>1时，情况类似上面提到过的谜题，若first的最先操作使得剩下的水龙头为偶数，如果你能把剩下的取完那就直接胜利，如果不能那就拿走中间的若干个偶数个硬币使得剩下的硬币被分为数目相等的两堆。接着对方对某堆进行操作你就对另一堆进行同样的操作，这时是second wins。first的最先操作使得剩下的水龙头为奇数时同理可证second wins。

那就OK了。

使剩下的队列满足a1 < a2 < a3 ... < a(i ) <=> a(i+1) > a(i+2) > .. a(n-1) > a(n)

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>

int d[1010],rev[1010],index[10];
double hi[1010];

int main()
{
    int n,tmp=0,i,j,max=0,ct=0;
    double db;
    scanf("%d",&n);
    for(i=0;i<n;++i)
    {    scanf("%lf",&hi[i]);//双精度浮点数输入须为%lf，而非%f
        d[i]=1;
        rev[i]=1;
    }
    //scanf("%f",&db);
    //d[0]=1;
    for(i=1;i<n;++i)
    {
        for(j=0;j<i;++j)
            if(hi[j]<hi[i]&&d[j]+1>d[i])
                d[i]=d[j]+1;//正序以i结尾的最长上升子序列长度
    }
    for(i=n-1;i>=0;--i)
    {
        for(j=n-1;j>i;--j)
            if(hi[j]<hi[i]&&rev[i]<rev[j]+1)
                rev[i]=rev[j]+1;//逆序以i结尾的最长上升子序列长度
    }
    for(i=0;i<n;++i)
    {
        if(d[i]+rev[i]>max)//find the highest one int the middle,keep its index in record
        {
            max=d[i]+rev[i];
            index[0]=i;
            tmp=0;
        }
        else if(d[i]+rev[i]==max&&hi[i]==hi[index[0]])//&&hi[i]==hi[index[0]]漏掉则出错。此条件判断是否有两个相等的最高顶点。
        {
            index[++tmp]=i;
        }
    }
    ct=index[0]+1-d[index[0]]+n-1-index[tmp]+1-rev[index[tmp]];//b4 and after of 3 parts:before index[0];between o~tmp;after index[tmp]
    for(i=index[0]+1;i<index[tmp];++i)//intermediate part
        if(hi[i]<hi[index[0]])ct++;
    printf("%d\n",ct);
    return 0;
}

给定你一个字符串，和n个单词构成的字典。让你求出在字符串中最小删去几个字母，使得剩下的字符串能够由字典中的若干个单词构成。输出最少删去的字母的个数。

分析
考虑给定字符串中第i个字符，可能删去，可能保留。——定义划分状态的关键。
d[i]=Min{d[i-1]+1,make(i)}//delete vs not delete

如果不删去，则它一定是作为某个单词的末尾。故与该位置前的状态有关系。make(i)中，要比较，所有字典中以msg[i]结尾的单词：若要保留，则此过程中删去字母个数ct,return 就是Min{d[该单词首字母的前一个字符位置]+ct}

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#define INF 1000000
#define MIN(a,b) (a)>(b)?(b):(a)
int N,L;
char dic[600][26],msg[305];
int f[305];//记录第i位前丢弃的最少字母数

int make(int m)
{
    int k,j,ct=0,n=m,t,re=INF;
    for(k=0;k<N;++k)
    {
        if(dic[k][strlen(dic[k])-1]==msg[m])//若写m为n此处n=0,WA
        {
            n=m;ct=0;
            j=strlen(dic[k])-1;
            
            while(j>=0)
            {
                while(n>=0&&msg[n]!=dic[k][j])
                {
                    n--;
                    ct++;
                }
                if(n>=0&&msg[n]==dic[k][j])n--;//当n小于0时说明此单词比该msgd第n位前的字串长
                else break;
                j--;
            }
            //if(j==-1&&ct+f[n-1]<re)
            //{
            //    re=ct+f[n-1];
            //    //t=n;
            //}
            if(j==-1)//说明字典中存在以msg【n】结尾的子串=该单词
            {
                if(n>=0&&ct+f[n]<re)//由于上一个if语句多减了一次1，所以此时perhaps n<0
                    re=ct+f[n];
                else if(n<0&&ct<re)re=ct;//此时说明msg中的该单词恰好是从msg[0]开始的
            }
        }
    }
    /**//*if(re==INF)头开始误导了，想着总是加一，不对。其实是对的，会自己判断选择到达该状态的其他路径，
        return f[m-1]==0?0:f[m-1]+1;                                故此处多余*/
        
    return re;
}
int main()
{
    int len,i,j,k;
    scanf("%d",&N);
    scanf("%d",&len);
    scanf("%s",msg);
    //for(i=0;i<len;i++)调试时的代码一定要记得注释掉！！！WA两次因此。太suck了
    //    printf("%c ",msg[i]);
    //printf("\n");
    //for(i=0;i<len;i++)
    //    printf("%-2d",i);
    //printf("\n");
    for(i=0;i<N;++i)
    {
        scanf("%s",dic[i]);
    }
    len=strlen(msg);
    f[0]=1;//初始状态可能不为1，即第一个字符也可能作为字典单词的最后一个字母，此时该单词位单字母单词
    for(i=0;i<N;++i)
        if(strlen(dic[i])==1&&dic[i][0]==msg[0])f[0]=0;
    for(i=1;i<len;i++)
    {
        f[i]=MIN(f[i-1]+1,make(i));
    }
    printf("%d\n",f[len-1]);
    
}