T1 多边形
就A了这一道/kk
疯狂的小细节：
- 这是个环！要断成链！！
-
你看样例里那个-7多显眼有没有什么启发？负数乘负数！乘完可能是个很大的正数！！ - 同时记录最大值最小值，赋初值要注意反着赋！求最小就先赋最大，求最大先赋最小
- DP的顺序已经有保证了，没必要再开bool数组判当前点和边用没用过
一开始被这个绕进去半天
code:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define maxn 110
using namespace std;
template<typename T>
inline void read(T &x){
x=0;bool flag=0;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') flag=1;
for(;isdigit(c);c=getchar()) x=x*10+(c^48);
if(flag) x=-x;
}
const int inf=0x7fffffff;
int n,p[maxn];
char e[maxn];
bool flag_e[maxn],flag_p[maxn];//没用！！
int ans,f[maxn][maxn][2],s[10],minn,maxx;
void dp(){
for(int j=2;j<=n;j++){
for(int i=1;i<=n;i++){
for(int k=1;k<j;k++){
int a=f[i][k][0],b=f[i][k][1],t=(i+k-1)%n+1,c=f[t][j-k][0],d=f[t][j-k][1];
if(e[t]=='t') minn=a+c,maxx=b+d;
else{
s[1]=a*c,s[2]=a*d,s[3]=b*c,s[4]=b*d;
minn=s[1];maxx=s[1];
for(int o=2;o<=4;o++){
minn=min(minn,s[o]);
maxx=max(maxx,s[o]);
}
}
f[i][j][0]=min(f[i][j][0],minn);
f[i][j][1]=max(f[i][j][1],maxx);
}
}
}
}
int main(){
read(n);
for(int i=1;i<=n;i++) {
cin>>e[i]>>p[i];
f[i][1][0]=p[i];f[i][1][1]=p[i];
}
for(int i=1;i<=n;i++){
for(int j=2;j<=n;j++){
f[i][j][0]=inf;//i为开头，长度为j的最小值
f[i][j][1]=-inf;//i为开头，长度为j的最大值
}
}
dp();
ans=-inf;
for(int i=1;i<=n;i++) ans=max(ans,f[i][n][1]);
cout<<ans<<endl;
return 0;
}
/*
4
t -7 t 4 x 2 x 5
*/
//33
T2 龙妹妹买牛奶
因为k只有1和2，所以从k入手分类讨论（不会k<=100和k<=n的情况，等神仙来讲）
- k==1 就是没有上司的舞会，父亲选了儿子就不能选
- k==2 在1上稍加修改，父亲选了儿子孙子都不能选
f[x][1]+=sum[y];
父亲不选，儿子可选0或1个，取个maxf[x][0]=max(f[x][0],f[y][1]+sum[x]-f[y][0]); - 我们也不知道一号点是选好还是不选好，就最后再取个max
code:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define maxn 100010
using namespace std;
template<typename T>
inline void read(T &x){
x=0;bool flag=0;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') flag=1;
for(;isdigit(c);c=getchar()) x=x*10+(c^48);
if(flag) x=-x;
}
int n,k,a[maxn],b[maxn];
int f[maxn][2];//0不选 1选
int cnt=1,head[maxn],rt[maxn],root,ans,sum[maxn];
bool vis[maxn];
struct node{
int nxt;
int to;
}e[2*maxn];
void add(int from,int to){
e[++cnt].to=to;
e[cnt].nxt=head[from];
head[from]=cnt;
}
void dp1(int x){
for(int i=head[x];i;i=e[i].nxt){
int y=e[i].to;
// cout<<"y"<<y<<" ";
dp1(y);
f[x][1]+=f[y][0];
f[x][0]+=max(f[y][0],f[y][1]);
// cout<<"f[x][]"<<f[x][1]<<" "<<f[x][0]<<endl;
}
}
void dp2(int x,int fa){
for(int i=head[x];i;i=e[i].nxt){
int y=e[i].to;
if(y==fa) continue;
dp2(y,x);
sum[x]+=f[y][0];
}
f[x][0]=sum[x];
for(int i=head[x];i;i=e[i].nxt){
int y=e[i].to;
if(y==fa) continue;
f[x][0]=max(f[x][0],f[y][1]+sum[x]-f[y][0]);
f[x][1]+=sum[y];
}
}
int main(){
read(n),read(k);
if(k==1){
for(int i=1;i<=n;i++) f[i][0]=0,f[i][1]=1;
for(int i=1;i<=n-1;i++){
read(a[i]),read(b[i]);
if(a[i]>b[i]) swap(a[i],b[i]);
add(a[i],b[i]);
rt[b[i]]=1;
}
for(int i=1;i<=n;i++){
if(rt[i]==0){
root=i;
break;
}
}
dp1(root);
ans=max(f[root][0],f[root][1]);
}
if(k==2){
for(int i=1;i<=n;i++) f[i][0]=0,f[i][1]=1;
for(int i=1;i<=n-1;i++){
read(a[i]),read(b[i]);
add(a[i],b[i]);
add(b[i],a[i]);
}
dp2(1,0);
ans=max(f[1][0],f[1][1]);
}
cout<<ans<<endl;
return 0;
}//100pts
/*
3 1
1 2
1 3
*/
//2
/*
3 2
1 2
1 3
*/
//1
T3 不要62
数位DP果然全是细节，不过经过本题爆零后对数位DP的理解又深了不少
写法1
solve(x)//[0,x]有多少符合要求的数
code:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define maxn 20
using namespace std;
template<typename T>
inline void read(T &x){
x=0;bool flag=0;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') flag=1;
for(;isdigit(c);c=getchar()) x=x*10+(c^48);
if(flag) x=-x;
}
int n,m;
int ans,len,num[maxn],f[maxn][maxn];
bool flag=0;
void pre(){
memset(f,0,sizeof(f));
f[0][0]=1;
for(int i=1;i<=9;i++){
for(int j=0;j<=9;j++){
if(j==4) continue;
for(int k=0;k<=9;k++){
if(!(j==6&&k==2)) f[i][j]+=f[i-1][k];
}
}
}
}
int solve(int x){
if(!x) return 1;//********
memset(num,0,sizeof(num));
ans=0,len=0;
while(x){
num[++len]=x%10;
x/=10;
}
// num[++len]=0;
for(int i=len;i>=1;i--){
for(int j=0;j<num[i];j++){
if(!(num[i+1]==6&&j==2)) ans+=f[i][j];
}
if((num[i]==4)||(num[i+1]==6&&num[i]==2)) break;
if(i==1) ++ans; //如果这个数自己是满足条件的，就把它也算上********
}
return ans;
}
int main(){
pre();
while(1){
read(n),read(m);
if(n==0&&m==0) return 0;
if(m<n) swap(n,m);
// cout<<"**"<<solve(m)<<"**"<<solve(n-1)<<endl;
cout<<solve(m)-solve(n-1)<<endl;
}
return 0;
}
/*
1 100
233 2333333
0 0
*/
//80
//1187893
/*
1 9999999
*/
//4435928(?
/*
4 4
*/
//0!!!
写法2
(来自wsy_jim)
cul[x]//[0,x)有多少符合要求的数
code:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<stack>
#include<bitset>
#include<cstring>
#define ll long long
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a<b)?a:b)
using namespace std;
const int INF=0x3f3f3f3f,N=15;
inline int read(){
int x=0,y=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') y=-1;c=getchar();}
while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x*y;
}
int l,r,f[N][N];
void init(){
memset(f,0,sizeof f);
f[0][0]=1;
for(int len=1;len<=7;len++)
for(int i=0;i<10;i++)
for(int j=0;j<10;j++)
if(i!=4&&!(i==6&&j==2)) f[len][i]+=f[len-1][j];
}
int cul(int x){
int op[N],len=0,res=0;
int n=x;
while(n){
op[++len]=n%10;
n/=10;
}
op[len+1]=0;
for(int i=len;i>0;i--){
for(int j=0;j<op[i];j++){
if(j!=4&&!(j==2&&op[i+1]==6)) res+=f[i][j];
}
if(op[i]==4||(op[i]==2&&op[i+1]==6)) break;
}
return res;
}
int main(){
init();
l=read(),r=read();
while(l!=0||r!=0){
//do something...
// cout<<cul(r+1)<<" "<<cul(l)<<endl;
printf("%d\n",cul(r+1)-cul(l));
l=read(),r=read();
}
return 0;
}