简单的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;
}
摘要: The ClocksIOI'94 - Day 2Consider nine clocks arranged in a 3x3 array thusly: |-------| |-------| |-------| | | | | | | | |---O | |---O | | O | | | | | | | |-------| |-------| |-------| A B C |-------|...
阅读全文
摘要: 这道题给了6个图，实际只需考虑5种（后两个相同）。最后一个模型自己没有抽象出来。还是逻辑清晰，比较不容易出错。头开始设许多临时变量，总是不知道具体值是多少，结果一直debug，还一直bug。。⊙﹏⊙b汗。。用4个rec结构记录比较好。最后一个模型，是左边两个，右边两个，然后根据两边上面矩形的高度情况，讨论矩形整体的宽。注意，自己设的变量最好还是写出来吧。此题竖着的边|，分别...
阅读全文
shit！太弱了!!警醒！这回思路完全正确、结构也很清晰。但是还是会忽略细节。习惯太差！继续打基础！！Go on！Keep up!
stack 模拟，一个数组就可以搞定.
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
int n,arr[100],stack[100],top=0;
char str[100];
void s2i(char* s)
{
int i=0;
while(*s)
{
arr[i++]=*s-'0';
s++;
}
}
void judge(int* ai)
{
int i,*pi=ai;
for(i=1;i<=n;i++)
{
if(*pi==i)
{
pi++;
continue;
}
else if(*pi>i)//push i
{
stack[top++]=i;
continue;
}
else if(*pi<i)//pop i
{
if(stack[--top]==*pi)
{
pi++;
i--;//忘记此处，这时i没有处理，需恢复
}
else
{
printf("no\n");
return;
}
}
}
while(top>0)
{
if(*pi!=stack[--top])
{
printf("no\n");
return;
}
else pi++;
}
printf("yes\n");
}
int main()
{
int t,k;
scanf("%d",&t);
while(t--)
{
top=0;
memset(str,0,sizeof(str));//此三处一再忘记复位，WA无数次。。！！！！！
memset(stack,0,sizeof(stack));
scanf("%d",&n);
scanf("%s",str);
s2i(str);
judge(arr);
}
return 0;
}
(1)思路：最长公共子序列：ans=L-LCS(s,^s)
(2)DP 状态：dp[i][j]为i to j，需要加入的字符。初始：dp[i][i]=0
分2种情况：s[i]==s[j]则dp[i][j]=dp[i+1][j-1]
s[i]!=s[j] =Min(dp[i+1][j],dp[i][j-1])+1
dp[i][j]=cal(i+1,j-1);
return dp[i][j];
}
/**//*dp[i][j]=MIN(cal(i+1,j-1)+2,cal(i+1,j)+1);
dp[i][j]=MIN(dp[i][j],cal(i,j-1)+1);*/
dp[i][j]=MIN(cal(i+1,j)+1,cal(i,j-1)+1);
return dp[i][j];
}
int main()
{
int i,j,k,mid;
scanf("%d",&N);
//for(i=0;i<N;i++)
scanf("%s",s);
len=strlen(s);
//printf("%d\n",len);
mid=len/2;
memset(dp,-1,sizeof(dp));//unsigned to the utmost
dp[mid][mid]=0;
printf("%d\n",cal(0,len-1));
return 0;
}
(3)节省空间，用dp[2][5002]的数组存放。因为i-1用过后，就不再用了
滚动数组最直接的想法就是利用原来第i-1行的空间来计算接下来要算的i+1行
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#define MIN(a,b) (a)<(b)?(a):(b)
char s[5002];
int dp[2][5002];
int main()
{
int i,j,k,l,N;
scanf("%d",&N);
scanf("%s",s);
for(i=N-1;i>=0;i--)
for(j=i+1;j<N;++j)
if(s[i]==s[j])dp[i&1][j]=dp[(i+1)&1][j-1];
else dp[i&1][j]=MIN(dp[(i+1)&1][j]+1,dp[i&1][j-1]+1);
printf("%d\n",dp[(i+1)%2][N-1]);
return 0;
}
这样就可以用一个array[2][]的数组，在两行之间交替计算
（4）
特殊情况：计算array[i][j]所用到的第i-1行的元素全部都在j列的左边
array[i-1][j]和array[i-1][j-1]
然后这种情况可以只用一维数组，按照从右到左的顺序计算
array[j] = array[j-1]+array[j]
重复i次
每次从右到左将一行的元素都按照array[j] = array[j-1]+array[j]计算
假设这个一维数组现在存的是i-1行的元素，计算第i行的元素时，直接将它记
录在这个一维数组对应的位置上
因为是从右向左计算，而计算只需要左边的元素，所以新存进去的元素不会影响后面元素的值
#include <stdio.h>
#include <string.h>
int main()
{
char a[5002];
int f[5002];
int i,j,n,t,tp;
scanf("%d%s",&n,a+1);
memset(f,0,sizeof(f));
for(i=1;i<=n;i++){
tp=0; //f[i-1,j-1]复位，一开始忘记了，老是wa，郁闷
for(j=n;j>=1;j--){
if(a[i]==a[j]){
t=f[j];
f[j]=tp+1; //f[i,j]=f[i-1,j-1]+1
tp=t;
}
else{
tp=f[j];
if(f[j]<f[j+1]) f[j]=f[j+1]; //f[i-1,j]<f[i,j-1]
}
}
}
printf("%d\n",n-f[1]);
return 0;
}
题意：
n个士兵，选ct个人出队，使得重新排队得到的队伍每个人都可以向左或向右看到无穷远，没有比他高或同样高的视觉障碍（人）。求ct最小值。
分析：
要从左无障碍的看到无限远，则需有左边的人都比他低，同理，右边也一样。故找到站到中间的一个人（or two），他的两边的最长子序列之和最大。即留下的士兵最多，即出队的人最少。
使剩下的队列满足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]);
}
摘要: 回文串不考虑除字母以外的字符，并且不区分大小写。strupr()usaco不让用，可能toupper可以。strcat(s1,s2)中s1必须为数组才可以不报错。while(fgets(line,100,fin)!=NULL)读入的一行包括结尾的换行符。注意处理大小写情况。第一种方法在usaco的test8中超时了。第二种，网上查的DP方法，讨论奇偶性，高效简单快捷。（1）暴搜。每读入一行，从此行...
阅读全文