【ZJ选讲·画山】

给出一张纸（N × M），你要在上面画山，但不能画出界（N,M<=100）

Like this： 起点为（0,0），终点为（N，0）

给出w种线段画法（x,y），表示用了这种画法后，笔迹末端点从（a,b）->（a+x,b+y）

（好吧，还是叫它向量吧）（x > 0） 每种画法可以用无数次，问可以画出多少种形状不同的山。

【题解】

          ①为了防止重复,可以将状态加一位表示上一次转移的斜率

          ②但是这样依旧会重复,因此直接按斜率分组使用背包跑出说所有转移来源就是了

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define ll long long

using namespace std;

const ll mod=1000000007;

struct segment{

	int a,b;

	bool operator <(const segment &rtm) const{

		return b*rtm.a<rtm.b*a;

	}

}seg[105];

struct group{

	int a,b;

	bool can[105];

}gro[105];

ll dp[105][105][105],s[105][105];

int gnt,n,m,p;

int main(){

	scanf("%d%d%d",&n,&m,&p);

	for(int i=1;i<=p;i++) scanf("%d%d",&seg[i].a,&seg[i].b);

	sort(seg+1,seg+p+1);

	int st=1; bool *f;

	for(int I=1;I<=p+1;I++){

		if(I==p+1||(seg[I].b*seg[st].a!=seg[I].a*seg[st].b)){

			++gnt;

			gro[gnt].a=seg[st].a;

			gro[gnt].b=seg[st].b;

			f=gro[gnt].can; f[0]=1;

			for(int i=st;i<I;i++)

				for(int j=seg[i].a;j<=n;j++)

					f[j]=f[j]|f[j-seg[i].a];

			st=I;

		}

	}

	s[0][0]=1;

	for(int i=0;i<=n;i++)

		for(int j=0;j<=m;j++)

			for(int k=1;k<=gnt;k++){

				for(int o=1;o<=n;o++) if(gro[k].can[o]){

					int ii=o,jj=ii*gro[k].b/gro[k].a;

					if(i-ii<0||j-jj<0||j-jj>m) break;

					dp[i][j][k]=(dp[i][j][k]+s[i-ii][j-jj]-dp[i-ii][j-jj][k]+mod)%mod;

				}

				s[i][j]=(s[i][j]+dp[i][j][k]+mod)%mod;

			}

	printf("%lld",s[n][0]);

	return 0;

}//*ZJ

.