专题训练--分数规划&整数划分

题目链接

知识盲点：最小比率生成树、01分数划分、整数划分 -五边形定理、

个人感觉上面的知识对我来说有点难，先放着，以后遇到题再学吧

整数拆分*

整数拆分五边形原理*

A - Dropping tests  POJ - 2976 

参考做法来自：博客

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <math.h>
#include <limits>
#include <set>
#include <map>
using namespace std;
int n,k,a[2333],b[2333];
double ps[2333];
bool ok(double x)
{
    for(int i=1;i<=n;i++) ps[i]=a[i]-x*b[i];
    sort(ps+1,ps+1+n);
    double ans=0;
    for(int i=n;i>=k+1;i--) ans+=ps[i];
    return ans>=0;
}
void sol()
{
    for(int i=1;i<=n;i++) scanf("%d",a+i);
    for(int i=1;i<=n;i++) scanf("%d",b+i);
    double l=0,r=1;
    while(r-l>1e-6)
    {
        double mid=(l+r)/2;
        if(ok(mid)) l=mid; else r=mid;
    }
    printf("%.0f\n",l*100);
}
int main()
{
    while(scanf("%d%d",&n,&k),n|k) sol();
}

D - UNIMODAL PALINDROMIC DECOMPOSITIONS

 POJ - 1221 

没太懂。

 

E - 放苹果 POJ - 1664 

然后E、F、I都是一类经典简单的划分dp题了。

小范围直接dp即可。

#pragma GCC optimize(2)
#include<cstdio>
#include<cstring>
#include<iostream>

#define ll long long
#define maxn 1005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

inline ll read()
{
	ll x=0,w=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
	return w==1?x:-x;
}
ll dp[20][20];
void add(ll &x,ll y)
{
    x=x+y;
}
int main()
{
    int _;cin>>_;while(_--)
    {
        int n,m;
        //cin>>m>>n;
        scanf("%d%d",&m,&n);
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;
        for(int i=1;i<=n;++i){
            for(int j=0;j<=m;++j){
                //dp[i][j]=dp[i-1][j]
                add(dp[i][j],dp[i-1][j]);
                if(j-i>=0)add(dp[i][j],dp[i][j-i]);
            }
        }
        printf("%lld\n",dp[n][m]);
    }
}

H - Partition HDU - 4651 

那么H题就是E题的进阶板，题意都是一样的，这里的n<=1e5,数据大了

方法1：oeis 写公式

方法2：五边形数定理，我看了半天没太懂，先搁着吧

oeis：

*:

大概就是这样的，容斥下

#include<stdio.h>
#define mod 1000000007
__int64 f[100005];
int w[100005];
int main()
{
	int p=1,t,n;
	w[0]=0;
	for(int i=1;w[p-1]<=100000;i++){
		w[p++]=i*(3*i-1)/2;
		w[p++]=i*(3*i+1)/2;
	}
	f[0]=1;
	for(int i=1;i<=100000;i++){
		f[i]=0;
		for(int j=1;i>=w[j];j++){
			if(((j-1)>>1)&1) f[i]=(f[i]-f[i-w[j]])%mod;
			else f[i]=(f[i]+f[i-w[j]])%mod;
		}
	}
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		printf("%I64d\n",(f[n]+mod)%mod);  //f数组中保存的数有负数。 
	}
	return 0;
}